Time-complexity of nested for loop

Question

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.

• user40980: On CS.SE: Big O: Nested For Loop With Dependence says its O(n^2).

Answer 1

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(n²).

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

• Benjamin Brumfield: Well, he is summing the numbers from 1 to n-1, but yes, the concept and everything else is correct.

Answer 2

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

Answer 3

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

Answer 4

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]