What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop?
Big ONested LoopsBig O Problem Overview
What is the Big-O time complexity of the following nested loops:
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
System.out.println("i = " + i + " j = " + j);
}
}
Would it be O(N^2) still?
Big O Solutions
Solution 1 - Big O
Yep, it's still O(n^2), it has a smaller constant factor, but that doesn't affect O notation.
Solution 2 - Big O
Yes. Recall the definition of Big-O: O(f(n)) by definition says that the run time T(n) ≤ kf(n) for some constant k. In this case, the number of steps will be (n-1)+(n-2)+...+0, which rearranges to the sum of 0 to n-1; this is
T(n)=(n-1)((n-1)+1)/2.
Rearrange that and you can see that T(n) will always be ≤ 1/2(n²); by the definition, thus T(n) = O(n²).
Solution 3 - Big O
It's N squared if you ignore the System.out.println. If you assume that the time taken by that will be linear in its output (which it may well not be, of course), I suspect you end up with O ( (N^2) * log N).
I mention this not to be picky, but just to point out that you don't just need to take the obvious loops into account when working out complexity - you need to look at the complexity of what you call as well.
Solution 4 - Big O
If you had N = 10, you iterations would be: 10+9+8+7+6+5+4+3+2+1. (this is: ten iterations plus nine iterations plus eight iterations... etc.).
Now, you need to find into the addition how many times you can get a N (10 in the example):
1:(10), 2:(9+1), 3:(8+2), 4:(7+3), 5:(6+4). Which is 5 times... and rests 5 iterations.
Now you know that you have five tens + 5:
10(5) + 5
In terms of f(n) (or N), we can easily see that this would be:
f(n) = n(n/2) + n/2 = (n^2)/2 + n/2 = (n^2 + n)/2... this is exactly the complexity of these nested loop.
But, considering the asymptotic behavior of Big O, we can get rid of the less significant values of f(n), which are the single n and the denominator.
Result: O(n^2)
Solution 5 - Big O
Yes, it would be N squared. The actual number of steps would the sum of 1 to N, which is .5*(N - 1)^2, if I'm not mistaken. Big O only takes into account the highest exponant and no constants, and thus, this is still N squared.
Solution 6 - Big O
Let us trace the number of times each loop executes in each iteration.
for (int i = 0; i < N; i++) { // outer loop
for (int j = i + 1; j < N; j++) { // inner loop
System.out.println("i = " + i + " j = " + j);
}
}
In the first iteration of the outer loop (i = 0), the inner loop executes N - 1 times.
In the second iteration of the outer loop (i = 1), the inner loop executes N - 2 times.
In the third iteration of the outer loop (i = 2), the inner loop executes N - 3 times.
. . .
In the N - 2th iteration of the outer loop (i = N - 3), the inner loop executes 2 times.
In the N - 1th iteration of the outer loop (i = N - 2), the inner loop executes 1 time.
In the last (Nth) iteration of the outer loop (i = N - 1), the inner loop executes 0 times.
Therefore, the total number of times this code executes is
N - 1 + N - 2 + N - 3 + … + 2 + 1 + 0
= 0 + 1 + 2 + … + N - 3 + N - 2 + N - 1
Substituting this in the Sum of Natural numbers Formula,
= (N - 1)((N - 1) + 1) / 2
= (N - 1)(N) / 2
= ((N^2) - N) / 2
= O(N^2), assuming System.out.println executes in constant time O(1).
——————
Also, do take a look at these
Solution 7 - Big O
For the given program:
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
println(...);
Consider n = 3:
i will have the values 0, 1 and 2.
For i = 0: println will execute 3 times
for i = 1: println will execute 2 times
for i = 2: println will execute 1 times
Thus the println function will execute 3 + 2 + 1 times, i.e. n(n+1)/2 times.
Hence O(n(n+1)/2) = O(n^2).
Solution 8 - Big O
AFAIL, being begun from inner loop through outer ones is adequate way for calculation of nested loop complexity.
