CODEWITHSUNDEEP
javaloopscomplexity-theorybig-onested-loops
Kailua Bum
Kailua Bum

Reputation: 1368

Java Big O notation of 3 nested loops of log(n)

What would the Big O notation be for the following nested loops?

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

My thoughts are: each loop is O(log2(n)) so is it as simple as multiply

O(log2(n)) * O(log2(n)) * O(log2(n))  =  O(log2(n)^3)

Upvotes: 6

Views: 5469

Answers (3)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

Indeed, your assumption is correct. You can show it methodically like the following:

enter image description here

Upvotes: 0

Subhrajyoti Majumder
Subhrajyoti Majumder

Reputation: 41200

Yes you are right.

Easy way to calculate - 

for(int i=0; i<n;i++){ // n times 
    for(int j=0; j<n;j++){ // n times
    }
}

This example of simple nested loop. Here Big-O of each loop O(n) and it is nested so typically O(n * n) which is O(n^2) actual Big-O. And in your case - 

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

Which is in nested loop where each loop Big-O is O(log(n)) so all together complexity would be O(log(n)^3)

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 372804

Yes, that is correct.

One way to figure out the big-O complexity of nested loops whose bounds do not immediately depend on one another is to work from the inside out. The innermost loop does O(log n) work. The second loop runs O(log n) times and does O(log n) work each time, so it does O(log2 n) work. Finally, the outmost loop runs O(log n) times and does O(log2 n) work on each iteration, so the total work done is O(log3 n).

Hope this helps!

Upvotes: 11

Related Questions