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

• 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]