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

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 because: * n/a *

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

Edited by Rashakil Fol because: * n/a *

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

Edited by invisal because: * n/a *

Rashakil Fol 978 Super Senior Demiposter Team Colleague

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.