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.
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(n2).
More about this particular problem can be read on CS.SE at Big O: Nested For Loop With Dependence
1
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]