Results 1 to 2 of 2

Math Help - asimptotic value of height of binary tree

  1. #1
    MHF Contributor
    Joined
    Nov 2008
    Posts
    1,401

    asimptotic value of height of binary tree

    prove that height of a binary tree with n leaves is \Omega(log_{2}n)

    ?
    at level 0 we have 1 leaf
    at level 1 we have 2 leaves
    etc..
    2^{0}+2^{1}+2^{2}+..+2^{x}=n

    so the sum is 2^{x+1}-1=n

    x=log_{2}(n+1)-1

    and x\in\Omega(log_{2}n)
    and futher more x\in\theta(log_{2}n)

    first question:
    what formula did they use to calculate the sum
    (i have here q>1)
    ?
    second question:
    i know the definition of \Omega

    it means that our x is lagrer equal to C*log_{2}n

    \theta<br />
means that x is bounded by to functions
    i cant see how they got to the conclution that x\in\Omega(log_{2}n)<br />
and futher more x\in\theta(log_{2}n)<br />
    ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: asimptotic value of height of binary tree

    Quote Originally Posted by transgalactic View Post
    at level 0 we have 1 leaf
    at level 1 we have 2 leaves
    etc..
    2^{0}+2^{1}+2^{2}+..+2^{x}=n

    so the sum is 2^{x+1}-1=n

    x=log_{2}(n+1)-1
    Do you mean "n leaves" or "n nodes"? If leaves, then why is there a sum from 0 to x?

    Second, considering this sum assumes that the binary tree is perfect. It is rather obvious that a perfect tree has the least height for a given number of nodes, but it may require some thought to show it formally, and it has to be at least stated.

    Quote Originally Posted by transgalactic View Post
    and futher more x\in\theta(log_{2}n)
    I assume you mean \Theta(\log_{2}n).

    Quote Originally Posted by transgalactic View Post
    first question:
    what formula did they use to calculate the sum
    (i have here q>1)
    I don't know what q means. This is the sum of geometric progression.

    Quote Originally Posted by transgalactic View Post
    i cant see how they got to the conclution that x\in\Omega(log_{2}n) and futher more x\in\theta(log_{2}n)
    We have \log_2(n+k)=O(\log_2(n)) because \log_2(n+k)\le\log_2(2n)\le\log_22+\log_2n=1+\log_  2n\le2\log_2n for n\ge k and n\ge2.

    Also, \log_2n-k\in\Omega(\log_2n) because \log_2n-k\ge\frac{1}{2}\log_2n when \log_2n\ge2k, i.e., n\ge2^{2k}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. binary tree math proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 14th 2012, 04:24 AM
  2. Binary Tree Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 5th 2011, 08:40 PM
  3. Induction for binary tree.
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 30th 2010, 12:17 PM
  4. Finding the height of a tree
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: May 2nd 2009, 03:24 PM
  5. [SOLVED] Binary tree - number of leafs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 3rd 2008, 09:11 AM

Search Tags


/mathhelpforum @mathhelpforum