Results 1 to 2 of 2

Math Help - order of algorithms

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    7

    order of algorithms

    i'm normally decent with these type of problems but i can't really figure this one out.

    show that if n is a power of 2, say n = 2^k, then
    \sum_{i=0}^{k} log(n/2^i) = \Theta (lg^2 n)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Oct 2009
    Posts
    95
    Quote Originally Posted by Projectt View Post
    i'm normally decent with these type of problems but i can't really figure this one out.

    show that if n is a power of 2, say n = 2^k, then
    \sum_{i=0}^{k} log(n/2^i) = \Theta (lg^2 n)

    if n is a power of two then \sum_{i=0}^{k} log(n/2^i)  = \sum_{i=0}^{k} log(2^{k-i}) =\sum_{i=0}^{k} (k-i)log(2)  = log(2) \sum_{i=0}^{k} (k-i) \in \Theta(k^2) = \Theta([log_2(n)]^2) for some  k = log_2(n)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Algorithms
    Posted in the Math Software Forum
    Replies: 2
    Last Post: November 4th 2010, 09:25 PM
  2. Algorithms
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 8th 2010, 10:48 PM
  3. algorithms
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 16th 2010, 03:25 PM
  4. Algorithms
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 4th 2009, 12:33 PM
  5. Algorithms!
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 15th 2006, 04:03 AM

Search Tags


/mathhelpforum @mathhelpforum