Algorithm Execution Time

[nuzzle]

I think it is O(log n) but just wanted to get some confirmation to make sure I am approaching this correctly.

Say you had this expression in the loop instead,

x = 2*x

Then x would grow exponentially like this,

x = 2*2*2*.....*2*X = 2^i * X

where X is the initial value of x and i is the i'th iteration of the loop.

The loop ends when x exceeds n, namely when

2^i * X = n

If you divide by X and log2 both sides you get,

i = log2(n/X)

This shows the number of iterations it takes to finish the loop as a function of n. The runtime dependency of the loop on n is clearly O(log n).

-----

But you have this expression in the loop,

x = 2^x

and x will grow like this

x = 2^2^2^.....^2^X = 2^(2*2*2*.....*2*X) = 2^(2^i * X)

where X again is the initial value of x and i is the i'th iteration of the loop.

As above the loop ends when x exceeds n, namely when

2^(2^i * X) = n

Now if you log2 both sides once you get,

(2^i * X) = log2(n)

Then divide by X and log2 again.

i = log2(log2(n)/X)

This indicates the complexity is rather O(log log n) in this case.