Algorithm Execution Time
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: Algorithm Execution Time

  1. #1
    Join Date
    Apr 2010
    Posts
    2

    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.

  2. #2
    Join Date
    May 2009
    Posts
    2,413

    Re: Algorithm Execution Time

    Quote Originally Posted by ashkash View Post
    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.

  3. #3
    Join Date
    Apr 2010
    Posts
    2

    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?

  4. #4
    Join Date
    May 2009
    Posts
    2,413

    Re: Algorithm Execution Time

    Quote Originally Posted by ashkash View Post
    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center