Algorithm Execution Time

[ashkash]

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

x=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.

[mrnutty]

i would guess yes.

[Rashakil Fol]

i would guess yes.

You would guess wrong. If you consider computing 2^x to be a constant time operation, it's faster than log(n), but if you consider the actual cost of computing 2^x, it's slower than log(n).

[invisal]

If computing 2^x to be a constant time operation, it would be an O(1) algorithm. Because it grow too fast that it will always end at the fourth step of the loop. Let's look how big the number grow.

Step 1	: 2 ^ 2 		= 4
Step 2	: 2 ^ 4 		= 16
Step 3	: 2 ^ 16 		= 65,536
[B]Step 4	: 2 ^ 65,536 		= too big[/B]

[Rashakil Fol]

Going by that reasoning, any algorithm is constant time (or doesn't terminate) because computers have a finite amount of memory. That's not the point. Anyway, there's no clean function that would tell you how many iterations of 2^_ are needed to reach a given number.

[gashtio]

Assuming 2^n takes O(1) time, the complexity is O(log* n), that is, the iterated logarithm of n.

[invisal]

Going by that reasoning, any algorithm is constant time (or doesn't terminate) because computers have a finite amount of memory

Sorry that I made a false assumption because at that time I felt that there was no clear function to measure such complexity.

Assuming 2^n takes O(1) time, the complexity is O(log* n), that is, the iterated logarithm of n.

I have never known about this one. Thank for sharing. Nice one.
:$