# asimptotic value of height of binary tree

• November 20th 2011, 12:30 AM
transgalactic
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
$
means that x is bounded by to functions
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)
$

?
• November 20th 2011, 12:08 PM
emakarov
Re: asimptotic value of height of binary tree
Quote:

Originally Posted by transgalactic
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
and futher more $x\in\theta(log_{2}n)$

I assume you mean $\Theta(\log_{2}n)$.

Quote:

Originally Posted by transgalactic
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
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}$.