What's the time complexity of this while loop?

Question

while(n>x) 
  x*=x;

The correct answer is log(log(n)), I can see the log(n) since x^k>=n is when the while loop will stop. so I got to log(n), what am I missing?

P.S: it is given that x=2.

Answer 1

Let a be the original value of x, and assume a>1.

• After the first cycle, x=a**2
• After the second cycle, x=a**4
• After the third cycle, x=a**8
• ... After the k-th cycle, x = a**(2**k)

x >= n means

a**(2**k) >= n
2**k >= log(n)/log(a)
k >= log2(log(n)/log(a)) = log2(log(n))-log2(log(a))

Answer 2

Expand the loop (let x = 2) and you'll see:

  x =     2 
  x =     4 //   2 * 2
  x =    16 //   4 * 4
  x =   256 //  16 * 16 
  x = 65536 // 256 * 256
  ... 
  x = 2 ** (2 ** n) // you can prove this by induction

and so

  n = log(log(x))

you'll be quite right with n = log(x) estimation if you have x *= constant body, e.g. for the constant == 2 we have

  x = 2
  x = 4
  x = 8
  ...
  x == 2 ** n 

where n is just

  n = log(x)