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