# Thread: asimptotic value of height of binary tree

1. ## asimptotic value of height of binary tree

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

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

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

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

and $\displaystyle x\in\Omega(log_{2}n)$
and futher more $\displaystyle 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

$\displaystyle \theta$ means that x is bounded by to functions
i cant see how they got to the conclution that $\displaystyle x\in\Omega(log_{2}n)$ and futher more $\displaystyle x\in\theta(log_{2}n)$
?

2. ## Re: asimptotic value of height of binary tree

Originally Posted by transgalactic
at level 0 we have 1 leaf
at level 1 we have 2 leaves
etc..
$\displaystyle 2^{0}+2^{1}+2^{2}+..+2^{x}=n$

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

$\displaystyle 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.

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

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.

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

Also, $\displaystyle \log_2n-k\in\Omega(\log_2n)$ because $\displaystyle \log_2n-k\ge\frac{1}{2}\log_2n$ when $\displaystyle \log_2n\ge2k$, i.e., $\displaystyle n\ge2^{2k}$.