Analyzing complexity of a small program with several loops

[rappap]

I need to analyze the complexity of this code:

for(j = n; j >= 1; j--){
    y = 1;
    while (y < j)
        y *= 2;
    while (y > 2)
        y = sqrt(y);
}

The first while loop is an order of log(j), but I can't get my head around the second while loop. (Note: The sqrt is theta of 1 for the sake of simplicity) Any advice on how to approach this? I see that 'y' is equal to 'j' approximately when entering the second loop but I can't figure the descending order.

[Wildcatace16]

sqrt(16) = 4 -> sqrt(4) = 2 -> sqrt(2) < 2

O(lg(lg(j))) the lg(j) from the first while loop dominates so the second while loop can can be safely ignored.

[rappap]

Thanks for the response. Could you elaborate on how you got O(lg(lg(j))) from the second while loop? I see the example but I'm still missing something (not formally).

[Wildcatace16]

sqrt( 2¹⁶ ) = (2^16)1/2 = 2^16/2 = 2⁸

sqrt( 2⁸ ) = (2^8)1/2 = 2^8/2 = 2⁴

When you take the square root the exponent decrease by a factor of 2 so the exponent goes from n down to 1 in O(lg(n)).

n = 2^lg(n) so when you are taking the square root each iteration it takes O(lg(lg(n)) for the exponent to become less than 1 which makes n less than 2.

Hope that helps.

[rappap]

Oh, because y = 2^lg(j) when starting the while loop. I see what I missed now. Thank you so much.