Algorithm Execution Time

[ashkash]

I need to figure out the execution time of the following algorithm in terms of n.

j=2
while (x < n) {
x=2^x
}

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

[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.

[ashkash]

Thanks for the response. I think it is a bit clearer.

I actually had a typo in the original algorithm and instead of j = 2 it should be x = 2 initially before entering the loop. But I guess the initial value of x does not make a difference to the runtime of the loop in terms of n.

So say I had this expression in the loop instead,

x = x * x

Then x would grow exponentially like this,

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

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

i = log base j (n/X)

In this case the runtime dependency of the loop on n would still be O(log n).

Would this be correct?

[nuzzle]

I actually had a typo in the original algorithm and instead of j = 2 it should be x = 2 initially before entering the loop. But I guess the initial value of x does not make a difference to the runtime of the loop in terms of n.


I suspected that and I've denoted the inital x value with X in the formulas.

Now say you have

x = x*x

This is the same as,

x = x^2

In the first loop iteration you get

x = X^2

Then in the second,

x = X^2^2

And generalized you have

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

As before the loop ends in iteration i for which

X^(2^i) = n

Now if you take log2 on both sides you get

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

Then you divide with log2(X) and take log2 again,

i = log2(log2(n)/log2(X))

So in my view also in this case you have an O(log log n) complexity.

-----

So as a summary, to me it looks like

x = 2*x

gives O(log n), while

x = 2^x

and

x = x^2

both lead to O(log log n).