What is the time complexity of this nested for loop?

Question

What would be the time complexity be of these lines of code?

Begin
 sum = 0
 For i = 1 to n do
 For j = i to n do
 sum = sum + 1
End

I want to say O(n) = 2n^2 + 1 but I'm unsure because of the i=j part.

• user14215102: For O() you get rid of all non-leading polynomial terms (+1) and multiplicative constants (2*), so you're talking about O(n^2).
• Mo B.: Note that 2n^2 + 1 = O(n) but not O(n) = 2n^2 + 1.

Answer 1

Your answer is correct!

A nested loop instinctively leads you to the right answer which is O(n^2). In doing Big-O analysis, it usually doesn't matter being specific to the point i.e. saying the time complexity is O(2n^2) or O(3n^2 + 1) -- saying O(n^2) is enough since that is the dominating task of the function.

The i = j condition simply makes it so that there are...

1. i=1: n operations
2. i=2: (n-1) operations
3. ...
4. i=n: 1 operation

So, the sum of all operations you do is 1 + 2 + ... n = n(n+1)/2 which is O(n^2).