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

Question

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)

Answer 1

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(log² n) work. Finally, the outmost loop runs O(log n) times and does O(log² n) work on each iteration, so the total work done is O(log³ n).

Hope this helps!

Answer 2

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

Answer 3

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)