Algorithm Execution Time

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