Time complexity calculation in a nested loop-CodePudding

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?

CodePudding user response：

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.