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?

Question

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?

Alienage

See also Time complexity of nested for loop. – Maines

Related post - What is the worst case time complexity for this algorithm?, Time-complexity of nested for loop & Big O: Nested For Loop With Dependence – Interatomic

Answer 1

Yep, it's still O(n^2), it has a smaller constant factor, but that doesn't affect O notation.

Thickset

In complete consideration for the question asked could you say this answer is a bit misleading? His questions explicitly asks: 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? His examples yes remains O(n^2) but for the broader question, if the second loop is a division of n (still dependent) wouldn't you get a logrithmic O(n) rather than n^2? I am jsut a student so do yell if I am wrong. – Outmaneuver

No: o(n log n) would require: for(int j = n; j > 0; j/=2) [which is a different domain: j=n to n/2]. whereas the loops are i=0 to N and j=i+1 to N, both are still processing the in a linear domain so: O(n) * O(n) = O(n^2) – Wetmore

Answer 2

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

Cant

Answer 3

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.

Began

You say it implicitly, but it should be noted explicitly that complexity depends on what you consider "unit of work". If println is unit of work, then it's O(n^2), if machine instruction is unit of work, then it's as you say. – Lecher

It's pretty odd for the unit of work to depend on n though - or at least, it makes it less useful in the real world, IMO. – Began

Can you tell me what the T(n) is? – Albin

@Imray: I'm not sure what you mean, I'm afraid. – Began

T(n) is the exact amount of executions, which can be summarized/simplified as something in Big-O. For example T(n) might be 2n^2 + 4n + 8 etc... – Albin

@Imray: Okay - in that case it depends on exactly what you're counting... the number of instructions? The number of loop bodies executed? (The latter would be 0 + 1 + ... + N-1, i.e. N^2 - N IIRC. – Began

I've tried to up-vote but the system says it will not accept it. – Partition

Answer 4

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

1. https://mcmap.net/q/271061/-what-is-the-worst-case-time-complexity-for-this-algorithm
2. https://mcmap.net/q/271060/-time-complexity-of-nested-for-loop
3. https://mcmap.net/q/271062/-o-n-and-time-complexity-function-of-the-given-code
4. https://mcmap.net/q/271063/-using-big-o-notation-what-is-the-correct-label-for-this-algorithm
5. https://mcmap.net/q/271064/-nested-for-loop-in-big-oh-complexity

Breslau

Answer 5

If you had N = 10, your 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 (N = 10 in my example):

1:(10), 2:(9+1), 3:(8+2), 4:(7+3), 5:(6+4). Which is 5 times... and still remains 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)

Reinaldoreinaldos

"Now, you need to find into the addition how many times you can get a N (10 in the example):" How did you come up with this? Sorry my maths is not good. – Inscription

Answer 6

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.

Beezer

You're off by just a bit - the sum from 1 to n is n*(n+1)/2, or .5*n^2+.5*n, which is clearly O(n^2). – Holy

Answer 7

AFAIL, being begun from inner loop through outer ones is adequate way for calculation of nested loop complexity.

Walkin

Answer 8

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

Antepenult