CODEWITHSUNDEEP
algorithmtime-complexity
daniel
daniel

Reputation: 148

Time complexity calculation in a nested loop

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?

Upvotes: 0

Views: 58

Answers (1)

collapsar
collapsar

Reputation: 17238

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.

Upvotes: 2

Related Questions