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

Question

What would Big O mean for the next 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: each cycle is equal to O(log2(n)) , so this is just how to multiply

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

Answer 1

Yes, that's right.

One way to find out the complexity of large O values ​​of nested loops whose boundaries do not immediately depend on each other is to work from the inside out. The innermost loop runs O (log n). The second loop runs O (log n) times, and O (log n) works every time, so O (log ² n) works. Finally, the topmost loop starts O (log n) times, and O (log ² n) runs on each iteration, so the overall work is done O (log ³ n).

Hope this helps!

Answer 2

Yes you are right.

A simple way to calculate is

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

This example is a simple nested loop. Here, the Big-O of each loop is O (n), and it is nested so typically O (n * n), which is O (n ^ 2) the 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++; } } } 

What is in the nested loop, where each Big-O loop is O(log(n)) , so all together will be O(log(n)^3)

Answer 3

In fact, your assumption is true. You can show this methodically as follows: