0

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
7 Years
Discussion Span
Last Post by invisal
0

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

0

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

0

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.

0

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.
:$

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.