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`

.