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