What is the time complexity of this while loop?

Question

while(n>x) x*=x; 

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

PS: it is given that x = 2.

Answer 1

Expand the loop (let x = 2 ) and you will 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 therefore

  n = log(log(x)) 

you will be absolutely right with the estimate n = log(x) if you have the body x *= constant , for example. for constant == 2 we have

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

where n just

  n = log(x) 

Answer 2

Let a be the initial 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 kth 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 3

Let x initial value, a , > 1 . Each time the value of x is an exponent of a , and the exponential doubles each time you square the number of each iteration.

So m'th term is given where m is the number of completed cycles. Therefore we need or , Oh really .

Answer 4

Edit: (Given x = 2)

Your answer will be correct if:

 while(n>x) x*=2; 

This means that the time to achieve the result is cut into half of each iteration .

But as time decreases by x , each iteration and x increases, you get O log(Log(n)) .

Log(n) is the complexity in which you skip half of each iteration (B-Tree).