
April 10th, 2010, 09:09 PM
#1
Algorithm Execution Time
I need to figure out the execution time of the following algorithm in terms of n.
j=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.

April 11th, 2010, 09:09 AM
#2
Re: Algorithm Execution Time
Originally Posted by ashkash
I think it is O(log n) but just wanted to get some confirmation to make sure I am approaching this correctly.
Say you had this expression in the loop instead,
x = 2*x
Then x would grow exponentially like this,
x = 2*2*2*.....*2*X = 2^i * X
where X is the initial value of x and i is the i'th iteration of the loop.
The loop ends when x exceeds n, namely when
2^i * X = n
If you divide by X and log2 both sides you get,
i = log2(n/X)
This shows the number of iterations it takes to finish the loop as a function of n. The runtime dependency of the loop on n is clearly O(log n).

But you have this expression in the loop,
x = 2^x
and x will grow like this
x = 2^2^2^.....^2^X = 2^(2*2*2*.....*2*X) = 2^(2^i * X)
where X again is the initial value of x and i is the i'th iteration of the loop.
As above the loop ends when x exceeds n, namely when
2^(2^i * X) = n
Now if you log2 both sides once you get,
(2^i * X) = log2(n)
Then divide by X and log2 again.
i = log2(log2(n)/X)
This indicates the complexity is rather O(log log n) in this case.
Last edited by nuzzle; April 11th, 2010 at 10:39 AM.

April 11th, 2010, 11:02 AM
#3
Re: Algorithm Execution Time
Thanks for the response. I think it is a bit clearer.
I actually had a typo in the original algorithm and instead of j = 2 it should be x = 2 initially before entering the loop. But I guess the initial value of x does not make a difference to the runtime of the loop in terms of n.
So say I had this expression in the loop instead,
x = x * x
Then x would grow exponentially like this,
x = x*x*x*.....*x*X = x^i * X
where X is the initial value of x and i is the i'th iteration of the loop.
i = log base j (n/X)
In this case the runtime dependency of the loop on n would still be O(log n).
Would this be correct?

April 11th, 2010, 01:00 PM
#4
Re: Algorithm Execution Time
Originally Posted by ashkash
I actually had a typo in the original algorithm and instead of j = 2 it should be x = 2 initially before entering the loop. But I guess the initial value of x does not make a difference to the runtime of the loop in terms of n.
I suspected that and I've denoted the inital x value with X in the formulas.
Now say you have
x = x*x
This is the same as,
x = x^2
In the first loop iteration you get
x = X^2
Then in the second,
x = X^2^2
And generalized you have
x = X^2^2^2^.....^2 = X^(2^i)
As before the loop ends in iteration i for which
X^(2^i) = n
Now if you take log2 on both sides you get
(2^i) * log2(X) = log2(n)
Then you divide with log2(X) and take log2 again,
i = log2(log2(n)/log2(X))
So in my view also in this case you have an O(log log n) complexity.

So as a summary, to me it looks like
x = 2*x
gives O(log n), while
x = 2^x
and
x = x^2
both lead to O(log log n).
Last edited by nuzzle; April 11th, 2010 at 01:10 PM.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
OnDemand Webinars (sponsored)
