Big O for 3 nested loops

Question

A Big O notation question...What is the Big O for the following code:

     for (int i = n; i > 0; i = i / 2){
        for (int j = 0; j < n; j++){
           for (int k = 0; k < n; k++){
              count++;
           }
        }
     }

My Thoughts: So breaking it down, I think the outside loop is O(log2(n)), then each of the inner loops is O(n) which would result in O(n^2 * log2(n)) Question #1 is that correct?

Question #2: when combining nested loops is it always just as simple as multiply the Big O of each loop?

1) Yes 2) Only if the loops don'T depend on each other. – Dan Jan 24 '13 at 21:05 — Dan, Jan 24 '13 at 21:05
You can multiply them if they are independent. – Peter Lawrey Jan 24 '13 at 21:06 — Peter Lawrey, Jan 24 '13 at 21:06

score 15 · Accepted Answer · answered Jan 24 '13 at 21:05

When loop counters do not depend on one another, it's always possible to work from the inside outward.

The innermost loop always takes time O(n), because it loops n times regardless of the values of j and i.

When the second loop runs, it runs for O(n) iterations, on each iteration doing O(n) work to run the innermost loop. This takes time O(n²).

Finally, when the outer loop runs, it does O(n²) work per iteration. It also runs for O(log n) iterations, since it runs equal to the number of times you have to divide n by two before you reach 1. Consequently, the total work is O(n² log n).

In general, you cannot just multiply loops together, since their bounds might depend on one another. In this case, though, since there is no dependency, the runtimes can just be multiplied. Hopefully the above reasoning sheds some light on why this is - it's because if you work from the inside out thinking about how much work each loop does and how many times it does it, the runtimes end up getting multiplied together.

Hope this helps!

score 3 · Answer 2 · answered Jan 24 '13 at 21:05

3

Yes, this is correct: the outer loop is logN, the other two are N each, for the total of O(N^2*LogN)
In the simple cases, yes. In more complex cases, when loop indexes start at numbers indicated by other indexes, the calculations are more complex.

answered Jan 24 '13 at 21:05

Sergey Kalinichenko

714,442
84
1,110
1,523

Lack · Answer 3 · 2013-01-24T21:50:07.480

To answer this slightly (note: slightly) more formally, say T(n) is the time (or number of operations) required to complete the algorithm. Then, for the outer loop, T(n) = log n*T2(n), where T2(n) is the number of operations inside the loop (ignoring any constants). Similarly, T2(n) = n*T3(n) = n*n.

Then, use the following theorem:

If f₁(n) = O(g₁(n)) and f₂(n) = O(g₂(n)), then f₁(n)×f₂(n) = O(g₁(n)×g₂(n))
(source and proof)

This leaves us with T(n) = O(n²logn).

"Combining nested loops" is just an application of this theorem. The trouble can be in figuring out exactly how many operations each loop uses, which in this case is simple.

score 0 · Answer 4 · answered Apr 15 '14 at 12:51

0

You can proceed formally using Sigma Notation, to faithfully imitate your loops:

enter image description here

answered Apr 15 '14 at 12:51

Mohamed Ennahdi El Idrissi

2,931
2
19
32

Big O for 3 nested loops

4 Answers4

Linked