asimptotic value of height of binary tree

prove that height of a binary tree with n leaves is

?

at level 0 we have 1 leaf

at level 1 we have 2 leaves

etc..

so the sum is

and

and futher more

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

means that x is bounded by to functions

i cant see how they got to the conclution that and futher more

?

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

so the sum is

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

I assume you mean .

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

and futher more

We have because for and .

Also, because when , i.e., .