Time complexity calculation in a nested loop

Question

I've got the following code

1 for (i = 0; i < n; i++) 
2 for (j = 0; j < i; i++)
3 result = result + 1;

I know the time complexity is O(n^2) but I'm having trouble calculating it the way we're supposed to as explained by the materials we were given.

The time complexity of a loop, according to said materials, is

T = T1 + n(T1 + T2)

where T1 is the loop condition and T2 is the instruction inside the loop. When applying it to the exercise I get:

T = T1 + n(T1 + T2-3) 
 = T1 + n(T1 + T2 + (1+2+3...+n)(T2 + T3)).

As T1, T2 and T3 are all O(1), we get that

T = n * (1+2+3+...+n)
 = n * n * (n+1) / 2 
 = n^3.

But that is obviously wrong, so... what am I doing wrong?

• daniel: Thanks for the formatting. I'll be more careful next time :)
• TomekK: Where did you get (1+2+3...+n) from?
• daniel: It's the number of times the inner loop runs. First time 0, second time 1, third time 2, and so on up to n times the last time when j = n-1

Answer 1

Your derivation is wrong at the expansion of T2-3:

T2-3 = T2 + i * ( T2 + T3 )
 < T2 + n * ( T2 + T3 )
 = O(n)

You did not analyze the inner loop in isolation but took into account the outer loop iteration a second time in writing down the summation. Therefore you came up with an extra factor of n.

• daniel: Thanks! I understand it now :D