Time complexity of a simple java piece of code

Question

I have the following piece of code and I know that is has a big-O complexity of n*(log2(n))^2, but I can't understand why the first two loops have a complexity of log2(n) each. Can someone explain me why is that? Thanks.

for (int i = n; i>0; i/=2) {
   for (int j = 1; j < n; j*=2) {
       for (int k = 0; k < n; k+=2) { 
              ... // constant time number of operation
        }
    }
}

Answer 1

The first loop do O(log(n)) iterations because the values of i are equal to n divided by powers-of-two numbers like n, n/2, n/4, n/8, .., 1. Indeed, to reach 0, i must be divided by 2 at least iCount=floor(log(n)+1) times since n < 2^iCount and thus n / (2^iCount) < 1.

The second loop do O(log(n)) iterations because the values of j are powers-of-two numbers like 1, 2, 4, 8, 16, ... (the last possible value of j is 2^(floor(log(n))).

The third loop do O(n/2) iterations because the values of k are 0, 2, 4, 6, 8, ....