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.

Edited by ashkash: n/a

5
Contributors
6
Replies
8
Views
8 Years
Discussion Span
Last Post by invisal

i would guess yes.

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

Edited by Rashakil Fol: n/a

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]``````

Edited by invisal: n/a

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.

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