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.
ashkash 0 Newbie Poster
mrnutty 761 Senior Poster
i would guess yes.
Rashakil Fol 978 Super Senior Demiposter Team Colleague
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 381 Search and Destroy
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 978 Super Senior Demiposter Team Colleague
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 25 Light Poster
Rashakil Fol commented: yes +7
invisal 381 Search and Destroy
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.
:$
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.