Time complexity of this while loop?

Question

What's the time complexity of this loop?

j=2
while(j <= n)
{
 //body of the loop is Θ(1)
 j=j^2
}

Answer 1

You have

j = 2

and each loop : j = j^2

The pattern is :

2 = 2^(2^0)
2*2 = 2^(2^1)
4*4 = 2^(2^2)
16*16 = 2^(2^3)

Which can be seen as :

2^(2^k) with k being the number of iteration

Hence loop stops when :

2^(2^k) >= n
log2(2^(2^k)) >= log2(n)
2^k >= log2(n)
log2(2^k) >= log2(n)
k >= log2(log2(n))

the complexity is log2(log2(n))

• Saeedeh: can you explain why it would be Log2(n)?
• Al_th: Yes sorry, i was on my mobile phone and planned to explain more when in front of a computer. And the answer was wrong on top of that ...