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)

$

?

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..

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

Quote:

Originally Posted by

**transgalactic** and futher more $\displaystyle x\in\theta(log_{2}n)$

I assume you mean $\displaystyle \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 $\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}$.