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?

Thanks for the formatting. I'll be more careful next time :) — daniel
– daniel, Commented May 2, 2022 at 14:25
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 — daniel
– daniel, Commented May 2, 2022 at 14:30

collapsar · Accepted Answer · 2022-05-02 14:30:42Z

2

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.

answered May 2, 2022 at 14:30

collapsar

17.4k5 gold badges40 silver badges66 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

daniel Over a year ago

Thanks! I understand it now :D

Collectives™ on Stack Overflow

Time complexity calculation in a nested loop

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related