# Time-complexity of nested for loop

I have loops like this:

``````for(int i = 0; i < n; i++) {
for(int j = 0; j < i; j++) {
sum += 1;
}
}
``````

It's O(n * ), but I'm not sure what the j < i loop is.

I have some tests that I ran,

``````n = 10, runs = 45

n = 20, runs = 190

n = 40, runs = 780

n = 80, runs = 3160

n = 10, runs = 12720
``````

It seems to be converging onto .5*n^2, but I'm not quite sure.

You are summing up the numbers from 1 to n, incrementing the value by one each time. This is essentially the classic Gauss sumation which is:

``````sum(1 .. n) = (n * n-1)/2
``````

This also happens to be the number of times through the loop.

``````(n^2 - n) / 2
(n^2)/2 - n/2
``````

When representing Big O, only term with the highest power is used and constants are thrown away, and thus the answer is O(n2).

More about this particular problem can be read on CS.SE at Big O: Nested For Loop With Dependence

• Well, he is summing the numbers from 1 to n-1, but yes, the concept and everything else is correct. Jan 22, 2014 at 14:15

On the 1st iteration of the outer loop (i = 0), the inner loop will iterate 0 times On the 2nd iteration of the outer loop (i = 1), the inner loop will iterate 1 time On the 3rd iteration of the outer loop (i = 2), the inner loop will iterate 2 times
.
.
On the FINAL iteration of the outer loop (i = n ‐ 1), the inner loop will iterate n ‐ 1 times

So, the total number of times the statements in the inner loop will be executed will be equal to the sum of the integers from 1 to n ‐ 1, which is:

``````((n ‐ 1)*n) / 2 = (n^2)/2 ‐ n/2 = O(n^2) times
``````

if i==0 then j ranges from 0 to -1 ==> (not possible) 0 if i==1 then j ranges from 0 to 0 ==> 1 if i==2 ,, ,, ,, 1 ==> 2 . . . if i==n-1 then j from 0 to n-2 ==> n-1 iterations

summing them

It is S = 0 + 1 + 2 + 3 +.......+ n-2 + n-1 same as S = n-1 + n-2 + ...... + 1 + 0

summing 2*S= (n-1) + (n-1) +.............(n-1) //n times

==> 2*S = (n-1)*n ==> S= (n-1)*n/2

You can see that it follows a particular equation which is `(n*(n-1))/2`. e,g for n=5, runs=(n*(n-1))/2=5*4/2=10.So it is O(n*(n-1))=O(n^n-n)=O(n^2)[As in case of Big-O, lower order terms and constants are ignored]