# 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?

### >Solution :

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`.