asimptotic value of height of binary tree

**transgalactic** · November 20th 2011, 12:30 AM

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 />$
?

**emakarov** · November 20th 2011, 12:08 PM

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.

Originally Posted by transgalactic

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

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

Thread: asimptotic value of height of binary tree

LinkBack

Thread Tools

Display

asimptotic value of height of binary tree

Re: asimptotic value of height of binary tree

Similar Math Help Forum Discussions

binary tree math proof

Binary Tree Question

Induction for binary tree.

Finding the height of a tree

[SOLVED] Binary tree - number of leafs

Search Tags