Explanation of why the height of a binary tree $theta(lg n)$.
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
From Heap Sort chapter of Introduction to algorithms :
Since a heap of $n$ elements is based on a complete binary tree , its
height is $theta(lg n)$.
I know this is correct but how can this be proved ?
algorithms trees binary
edited Aug 26 at 1:20
Michael Hardy
205k23187463
asked Aug 10 '12 at 8:55
Geek
92962040
add a comment |Â
up vote
2
down vote
favorite
From Heap Sort chapter of Introduction to algorithms :
Since a heap of $n$ elements is based on a complete binary tree , its
height is $theta(lg n)$.
I know this is correct but how can this be proved ?
algorithms trees binary
edited Aug 26 at 1:20
Michael Hardy
205k23187463
asked Aug 10 '12 at 8:55
Geek
92962040
1
Hint: prove that a complete binary tree of hight $h$ has $2^h$ elements
– pritam
Aug 10 '12 at 9:03
@pritam thats a pretty good way of coming to this conclusion . Can you throw an answer so that I can accept it as the accepted answer .
– Geek
Aug 10 '12 at 9:11
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
From Heap Sort chapter of Introduction to algorithms :
Since a heap of $n$ elements is based on a complete binary tree , its
height is $theta(lg n)$.
I know this is correct but how can this be proved ?
algorithms trees binary
edited Aug 26 at 1:20
Michael Hardy
205k23187463
asked Aug 10 '12 at 8:55
Geek
92962040
From Heap Sort chapter of Introduction to algorithms :
Since a heap of $n$ elements is based on a complete binary tree , its
height is $theta(lg n)$.
I know this is correct but how can this be proved ?
algorithms trees binary
edited Aug 26 at 1:20
Michael Hardy
205k23187463
asked Aug 10 '12 at 8:55
Geek
92962040
edited Aug 26 at 1:20
Michael Hardy
205k23187463
edited Aug 26 at 1:20
Michael Hardy
205k23187463
edited Aug 26 at 1:20
Michael Hardy
205k23187463
205k23187463
asked Aug 10 '12 at 8:55
Geek
92962040
asked Aug 10 '12 at 8:55
Geek
92962040
asked Aug 10 '12 at 8:55
Geek
92962040
92962040
1
Hint: prove that a complete binary tree of hight $h$ has $2^h$ elements
– pritam
Aug 10 '12 at 9:03
@pritam thats a pretty good way of coming to this conclusion . Can you throw an answer so that I can accept it as the accepted answer .
– Geek
Aug 10 '12 at 9:11
add a comment |Â
1
Hint: prove that a complete binary tree of hight $h$ has $2^h$ elements
– pritam
Aug 10 '12 at 9:03
@pritam thats a pretty good way of coming to this conclusion . Can you throw an answer so that I can accept it as the accepted answer .
– Geek
Aug 10 '12 at 9:11
1
1
Hint: prove that a complete binary tree of hight $h$ has $2^h$ elements
– pritam
Aug 10 '12 at 9:03
Hint: prove that a complete binary tree of hight $h$ has $2^h$ elements
– pritam
Aug 10 '12 at 9:03
@pritam thats a pretty good way of coming to this conclusion . Can you throw an answer so that I can accept it as the accepted answer .
– Geek
Aug 10 '12 at 9:11
@pritam thats a pretty good way of coming to this conclusion . Can you throw an answer so that I can accept it as the accepted answer .
– Geek
Aug 10 '12 at 9:11
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
2
down vote
accepted
If we write down the series counting the number of elements at each level of the tree, then we get
$$ mboxNumber of elements = n = 1 + 2 + 4 + 8 + ... + k tag1$$
That is, at the first level, there is only one node, the root of the tree. At the second level are the root's two children. At the third, each of those two children's two children (making the total four at the third level). And so on until the last level, in which there are $k$ leaves of the tree.
$n$ is a finite geometric series whose first element is $a = 1$, ratio is $r = 2$. Using the formula for a geometric series, we get:
$$ n = fraca(1 - r^i)1 - r = 2^i - 1 $$
We seek $i$, which is the number of elements in the sequence given by $(1)$:
$$ n = 2^i - 1 Rightarrow i = lceillg(n + 1)rceil $$
This means there are $lceillg(n + 1)rceil$ levels in the tree, or $lceillg(n + 1)rceil$ terms in the series in $(1)$. The ceiling is required because nodes taking up part of a level warrant an extra count to the number of levels. We're interested in the height of the tree, not the number of levels. A keen observation will reveal that the height $h$ of a complete binary tree is one less than the number of levels. In other words, the height is the number of plus signs in $(1)$. So the height $h$ of a complete binary tree in terms of its $n$ elements is
$$ h(n) = lceillg(n + 1)rceil - 1 tag2$$
To show that $h(n) in Theta(lg(n))$, first note the ceiling function will not affect the asymptotic behavior of $h(n)$, so the rounding up will be ignored for the rest of the discussion.
$h(n)$ is in $Theta(lg(n))$ if
$$ exists n_0 in mathbbN,; c_1, c_2 in mathbbR,; c_1, c_2 > 0 : c_1 lg(n) le lg(n + 1) - 1 le c_2 lg(n), quad forall n ge n_0 tag3$$
For the lower bound, let $c_1 = frac12$. Then we have:
$$frac12lg(n) = lg(sqrtn) le lg(n + 1) - 1, quad forall n ge 1 tag4$$
In $(4)$, $n_0 = 1$.
For the upper bound, let $c_2 = 2$. We have:
$$2lg(n) = lg(n^2) ge lg(n + 1) - 1, quad forall n ge 1 tag5$$
where $n_0 = 1$ here too.
So, for $c_1 = frac12$, $c_2 = 2$, and $n_0 = 1$, $(3)$ holds. Therefore
$h(n) in Theta(lg(n))$.
answered Aug 10 '12 at 11:26
ladaghini
48828
@ladadhini I changes my accepted answer as it has proved it rigorously . Can you explain a little bit more why the ceiling is required ?I guess the ceiling is required when it is near complete binary tree and not a complete binary tree ? Thanks .
– Geek
Aug 10 '12 at 11:31
@Geek: Yes, you're on the right track, though a complete binary tree, despite its name, permits the last level to not be "full." The reason we must round up is the same reason we round up for the following situation: if a school bus has a capacity of 30 children, how many buses are need to transport 100 children?
– ladaghini
Aug 10 '12 at 12:54
I have posted another question related to this here . can you try to clear my doubts on that too ?
– Geek
Aug 10 '12 at 13:03
add a comment |Â
up vote
3
down vote
Using induction one can prove that a full binary tree of height $h$ has $2^h-1$ elements. So you have $n=2^h-1$, i.e. $h=lg (n+1)=theta(lg n)$.
edited Aug 26 at 0:53
Oreo
33
answered Aug 10 '12 at 9:14
pritam
7,9611441
Shouldn't that be $2^h-1$?
– Mike
Aug 10 '12 at 9:17
@Mike the number of internal nodes in a complete binary tree is 2^h-1 .
– Geek
Aug 10 '12 at 9:21
@Mike Yeah you are correct, actually i was thiking $theta(2^h)$; anyway corrected it
– pritam
Aug 10 '12 at 9:27
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
If we write down the series counting the number of elements at each level of the tree, then we get
$$ mboxNumber of elements = n = 1 + 2 + 4 + 8 + ... + k tag1$$
That is, at the first level, there is only one node, the root of the tree. At the second level are the root's two children. At the third, each of those two children's two children (making the total four at the third level). And so on until the last level, in which there are $k$ leaves of the tree.
$n$ is a finite geometric series whose first element is $a = 1$, ratio is $r = 2$. Using the formula for a geometric series, we get:
$$ n = fraca(1 - r^i)1 - r = 2^i - 1 $$
We seek $i$, which is the number of elements in the sequence given by $(1)$:
$$ n = 2^i - 1 Rightarrow i = lceillg(n + 1)rceil $$
This means there are $lceillg(n + 1)rceil$ levels in the tree, or $lceillg(n + 1)rceil$ terms in the series in $(1)$. The ceiling is required because nodes taking up part of a level warrant an extra count to the number of levels. We're interested in the height of the tree, not the number of levels. A keen observation will reveal that the height $h$ of a complete binary tree is one less than the number of levels. In other words, the height is the number of plus signs in $(1)$. So the height $h$ of a complete binary tree in terms of its $n$ elements is
$$ h(n) = lceillg(n + 1)rceil - 1 tag2$$
To show that $h(n) in Theta(lg(n))$, first note the ceiling function will not affect the asymptotic behavior of $h(n)$, so the rounding up will be ignored for the rest of the discussion.
$h(n)$ is in $Theta(lg(n))$ if
$$ exists n_0 in mathbbN,; c_1, c_2 in mathbbR,; c_1, c_2 > 0 : c_1 lg(n) le lg(n + 1) - 1 le c_2 lg(n), quad forall n ge n_0 tag3$$
For the lower bound, let $c_1 = frac12$. Then we have:
$$frac12lg(n) = lg(sqrtn) le lg(n + 1) - 1, quad forall n ge 1 tag4$$
In $(4)$, $n_0 = 1$.
For the upper bound, let $c_2 = 2$. We have:
$$2lg(n) = lg(n^2) ge lg(n + 1) - 1, quad forall n ge 1 tag5$$
where $n_0 = 1$ here too.
So, for $c_1 = frac12$, $c_2 = 2$, and $n_0 = 1$, $(3)$ holds. Therefore
$h(n) in Theta(lg(n))$.
answered Aug 10 '12 at 11:26
ladaghini
48828
@ladadhini I changes my accepted answer as it has proved it rigorously . Can you explain a little bit more why the ceiling is required ?I guess the ceiling is required when it is near complete binary tree and not a complete binary tree ? Thanks .
– Geek
Aug 10 '12 at 11:31
@Geek: Yes, you're on the right track, though a complete binary tree, despite its name, permits the last level to not be "full." The reason we must round up is the same reason we round up for the following situation: if a school bus has a capacity of 30 children, how many buses are need to transport 100 children?
– ladaghini
Aug 10 '12 at 12:54
I have posted another question related to this here . can you try to clear my doubts on that too ?
– Geek
Aug 10 '12 at 13:03
add a comment |Â
up vote
2
down vote
accepted
If we write down the series counting the number of elements at each level of the tree, then we get
$$ mboxNumber of elements = n = 1 + 2 + 4 + 8 + ... + k tag1$$
That is, at the first level, there is only one node, the root of the tree. At the second level are the root's two children. At the third, each of those two children's two children (making the total four at the third level). And so on until the last level, in which there are $k$ leaves of the tree.
$n$ is a finite geometric series whose first element is $a = 1$, ratio is $r = 2$. Using the formula for a geometric series, we get:
$$ n = fraca(1 - r^i)1 - r = 2^i - 1 $$
We seek $i$, which is the number of elements in the sequence given by $(1)$:
$$ n = 2^i - 1 Rightarrow i = lceillg(n + 1)rceil $$
This means there are $lceillg(n + 1)rceil$ levels in the tree, or $lceillg(n + 1)rceil$ terms in the series in $(1)$. The ceiling is required because nodes taking up part of a level warrant an extra count to the number of levels. We're interested in the height of the tree, not the number of levels. A keen observation will reveal that the height $h$ of a complete binary tree is one less than the number of levels. In other words, the height is the number of plus signs in $(1)$. So the height $h$ of a complete binary tree in terms of its $n$ elements is
$$ h(n) = lceillg(n + 1)rceil - 1 tag2$$
To show that $h(n) in Theta(lg(n))$, first note the ceiling function will not affect the asymptotic behavior of $h(n)$, so the rounding up will be ignored for the rest of the discussion.
$h(n)$ is in $Theta(lg(n))$ if
$$ exists n_0 in mathbbN,; c_1, c_2 in mathbbR,; c_1, c_2 > 0 : c_1 lg(n) le lg(n + 1) - 1 le c_2 lg(n), quad forall n ge n_0 tag3$$
For the lower bound, let $c_1 = frac12$. Then we have:
$$frac12lg(n) = lg(sqrtn) le lg(n + 1) - 1, quad forall n ge 1 tag4$$
In $(4)$, $n_0 = 1$.
For the upper bound, let $c_2 = 2$. We have:
$$2lg(n) = lg(n^2) ge lg(n + 1) - 1, quad forall n ge 1 tag5$$
where $n_0 = 1$ here too.
So, for $c_1 = frac12$, $c_2 = 2$, and $n_0 = 1$, $(3)$ holds. Therefore
$h(n) in Theta(lg(n))$.
answered Aug 10 '12 at 11:26
ladaghini
48828
@ladadhini I changes my accepted answer as it has proved it rigorously . Can you explain a little bit more why the ceiling is required ?I guess the ceiling is required when it is near complete binary tree and not a complete binary tree ? Thanks .
– Geek
Aug 10 '12 at 11:31
@Geek: Yes, you're on the right track, though a complete binary tree, despite its name, permits the last level to not be "full." The reason we must round up is the same reason we round up for the following situation: if a school bus has a capacity of 30 children, how many buses are need to transport 100 children?
– ladaghini
Aug 10 '12 at 12:54
I have posted another question related to this here . can you try to clear my doubts on that too ?
– Geek
Aug 10 '12 at 13:03
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
If we write down the series counting the number of elements at each level of the tree, then we get
$$ mboxNumber of elements = n = 1 + 2 + 4 + 8 + ... + k tag1$$
That is, at the first level, there is only one node, the root of the tree. At the second level are the root's two children. At the third, each of those two children's two children (making the total four at the third level). And so on until the last level, in which there are $k$ leaves of the tree.
$n$ is a finite geometric series whose first element is $a = 1$, ratio is $r = 2$. Using the formula for a geometric series, we get:
$$ n = fraca(1 - r^i)1 - r = 2^i - 1 $$
We seek $i$, which is the number of elements in the sequence given by $(1)$:
$$ n = 2^i - 1 Rightarrow i = lceillg(n + 1)rceil $$
This means there are $lceillg(n + 1)rceil$ levels in the tree, or $lceillg(n + 1)rceil$ terms in the series in $(1)$. The ceiling is required because nodes taking up part of a level warrant an extra count to the number of levels. We're interested in the height of the tree, not the number of levels. A keen observation will reveal that the height $h$ of a complete binary tree is one less than the number of levels. In other words, the height is the number of plus signs in $(1)$. So the height $h$ of a complete binary tree in terms of its $n$ elements is
$$ h(n) = lceillg(n + 1)rceil - 1 tag2$$
To show that $h(n) in Theta(lg(n))$, first note the ceiling function will not affect the asymptotic behavior of $h(n)$, so the rounding up will be ignored for the rest of the discussion.
$h(n)$ is in $Theta(lg(n))$ if
$$ exists n_0 in mathbbN,; c_1, c_2 in mathbbR,; c_1, c_2 > 0 : c_1 lg(n) le lg(n + 1) - 1 le c_2 lg(n), quad forall n ge n_0 tag3$$
For the lower bound, let $c_1 = frac12$. Then we have:
$$frac12lg(n) = lg(sqrtn) le lg(n + 1) - 1, quad forall n ge 1 tag4$$
In $(4)$, $n_0 = 1$.
For the upper bound, let $c_2 = 2$. We have:
$$2lg(n) = lg(n^2) ge lg(n + 1) - 1, quad forall n ge 1 tag5$$
where $n_0 = 1$ here too.
So, for $c_1 = frac12$, $c_2 = 2$, and $n_0 = 1$, $(3)$ holds. Therefore
$h(n) in Theta(lg(n))$.
answered Aug 10 '12 at 11:26
ladaghini
48828
If we write down the series counting the number of elements at each level of the tree, then we get
$$ mboxNumber of elements = n = 1 + 2 + 4 + 8 + ... + k tag1$$
That is, at the first level, there is only one node, the root of the tree. At the second level are the root's two children. At the third, each of those two children's two children (making the total four at the third level). And so on until the last level, in which there are $k$ leaves of the tree.
$n$ is a finite geometric series whose first element is $a = 1$, ratio is $r = 2$. Using the formula for a geometric series, we get:
$$ n = fraca(1 - r^i)1 - r = 2^i - 1 $$
We seek $i$, which is the number of elements in the sequence given by $(1)$:
$$ n = 2^i - 1 Rightarrow i = lceillg(n + 1)rceil $$
This means there are $lceillg(n + 1)rceil$ levels in the tree, or $lceillg(n + 1)rceil$ terms in the series in $(1)$. The ceiling is required because nodes taking up part of a level warrant an extra count to the number of levels. We're interested in the height of the tree, not the number of levels. A keen observation will reveal that the height $h$ of a complete binary tree is one less than the number of levels. In other words, the height is the number of plus signs in $(1)$. So the height $h$ of a complete binary tree in terms of its $n$ elements is
$$ h(n) = lceillg(n + 1)rceil - 1 tag2$$
To show that $h(n) in Theta(lg(n))$, first note the ceiling function will not affect the asymptotic behavior of $h(n)$, so the rounding up will be ignored for the rest of the discussion.
$h(n)$ is in $Theta(lg(n))$ if
$$ exists n_0 in mathbbN,; c_1, c_2 in mathbbR,; c_1, c_2 > 0 : c_1 lg(n) le lg(n + 1) - 1 le c_2 lg(n), quad forall n ge n_0 tag3$$
For the lower bound, let $c_1 = frac12$. Then we have:
$$frac12lg(n) = lg(sqrtn) le lg(n + 1) - 1, quad forall n ge 1 tag4$$
In $(4)$, $n_0 = 1$.
For the upper bound, let $c_2 = 2$. We have:
$$2lg(n) = lg(n^2) ge lg(n + 1) - 1, quad forall n ge 1 tag5$$
where $n_0 = 1$ here too.
So, for $c_1 = frac12$, $c_2 = 2$, and $n_0 = 1$, $(3)$ holds. Therefore
$h(n) in Theta(lg(n))$.
answered Aug 10 '12 at 11:26
ladaghini
48828
answered Aug 10 '12 at 11:26
ladaghini
48828
answered Aug 10 '12 at 11:26
ladaghini
48828
answered Aug 10 '12 at 11:26
ladaghini
48828
48828
@ladadhini I changes my accepted answer as it has proved it rigorously . Can you explain a little bit more why the ceiling is required ?I guess the ceiling is required when it is near complete binary tree and not a complete binary tree ? Thanks .
– Geek
Aug 10 '12 at 11:31
@Geek: Yes, you're on the right track, though a complete binary tree, despite its name, permits the last level to not be "full." The reason we must round up is the same reason we round up for the following situation: if a school bus has a capacity of 30 children, how many buses are need to transport 100 children?
– ladaghini
Aug 10 '12 at 12:54
I have posted another question related to this here . can you try to clear my doubts on that too ?
– Geek
Aug 10 '12 at 13:03
add a comment |Â
@ladadhini I changes my accepted answer as it has proved it rigorously . Can you explain a little bit more why the ceiling is required ?I guess the ceiling is required when it is near complete binary tree and not a complete binary tree ? Thanks .
– Geek
Aug 10 '12 at 11:31
@Geek: Yes, you're on the right track, though a complete binary tree, despite its name, permits the last level to not be "full." The reason we must round up is the same reason we round up for the following situation: if a school bus has a capacity of 30 children, how many buses are need to transport 100 children?
– ladaghini
Aug 10 '12 at 12:54
I have posted another question related to this here . can you try to clear my doubts on that too ?
– Geek
Aug 10 '12 at 13:03
@ladadhini I changes my accepted answer as it has proved it rigorously . Can you explain a little bit more why the ceiling is required ?I guess the ceiling is required when it is near complete binary tree and not a complete binary tree ? Thanks .
– Geek
Aug 10 '12 at 11:31
@ladadhini I changes my accepted answer as it has proved it rigorously . Can you explain a little bit more why the ceiling is required ?I guess the ceiling is required when it is near complete binary tree and not a complete binary tree ? Thanks .
– Geek
Aug 10 '12 at 11:31
@Geek: Yes, you're on the right track, though a complete binary tree, despite its name, permits the last level to not be "full." The reason we must round up is the same reason we round up for the following situation: if a school bus has a capacity of 30 children, how many buses are need to transport 100 children?
– ladaghini
Aug 10 '12 at 12:54
@Geek: Yes, you're on the right track, though a complete binary tree, despite its name, permits the last level to not be "full." The reason we must round up is the same reason we round up for the following situation: if a school bus has a capacity of 30 children, how many buses are need to transport 100 children?
– ladaghini
Aug 10 '12 at 12:54
I have posted another question related to this here . can you try to clear my doubts on that too ?
– Geek
Aug 10 '12 at 13:03
I have posted another question related to this here . can you try to clear my doubts on that too ?
– Geek
Aug 10 '12 at 13:03
add a comment |Â
up vote
3
down vote
Using induction one can prove that a full binary tree of height $h$ has $2^h-1$ elements. So you have $n=2^h-1$, i.e. $h=lg (n+1)=theta(lg n)$.
edited Aug 26 at 0:53
Oreo
33
answered Aug 10 '12 at 9:14
pritam
7,9611441
Shouldn't that be $2^h-1$?
– Mike
Aug 10 '12 at 9:17
@Mike the number of internal nodes in a complete binary tree is 2^h-1 .
– Geek
Aug 10 '12 at 9:21
@Mike Yeah you are correct, actually i was thiking $theta(2^h)$; anyway corrected it
– pritam
Aug 10 '12 at 9:27
add a comment |Â
up vote
3
down vote
Using induction one can prove that a full binary tree of height $h$ has $2^h-1$ elements. So you have $n=2^h-1$, i.e. $h=lg (n+1)=theta(lg n)$.
edited Aug 26 at 0:53
Oreo
33
answered Aug 10 '12 at 9:14
pritam
7,9611441
Shouldn't that be $2^h-1$?
– Mike
Aug 10 '12 at 9:17
@Mike the number of internal nodes in a complete binary tree is 2^h-1 .
– Geek
Aug 10 '12 at 9:21
@Mike Yeah you are correct, actually i was thiking $theta(2^h)$; anyway corrected it
– pritam
Aug 10 '12 at 9:27
add a comment |Â
up vote
3
down vote
up vote
3
down vote
Using induction one can prove that a full binary tree of height $h$ has $2^h-1$ elements. So you have $n=2^h-1$, i.e. $h=lg (n+1)=theta(lg n)$.
edited Aug 26 at 0:53
Oreo
33
answered Aug 10 '12 at 9:14
pritam
7,9611441
Using induction one can prove that a full binary tree of height $h$ has $2^h-1$ elements. So you have $n=2^h-1$, i.e. $h=lg (n+1)=theta(lg n)$.
edited Aug 26 at 0:53
Oreo
33
answered Aug 10 '12 at 9:14
pritam
7,9611441
edited Aug 26 at 0:53
Oreo
33
edited Aug 26 at 0:53
Oreo
33
edited Aug 26 at 0:53
Oreo
33
33
answered Aug 10 '12 at 9:14
pritam
7,9611441
answered Aug 10 '12 at 9:14
pritam
7,9611441
answered Aug 10 '12 at 9:14
pritam
7,9611441
7,9611441
Shouldn't that be $2^h-1$?
– Mike
Aug 10 '12 at 9:17
@Mike the number of internal nodes in a complete binary tree is 2^h-1 .
– Geek
Aug 10 '12 at 9:21
@Mike Yeah you are correct, actually i was thiking $theta(2^h)$; anyway corrected it
– pritam
Aug 10 '12 at 9:27
add a comment |Â
Shouldn't that be $2^h-1$?
– Mike
Aug 10 '12 at 9:17
@Mike the number of internal nodes in a complete binary tree is 2^h-1 .
– Geek
Aug 10 '12 at 9:21
@Mike Yeah you are correct, actually i was thiking $theta(2^h)$; anyway corrected it
– pritam
Aug 10 '12 at 9:27
Shouldn't that be $2^h-1$?
– Mike
Aug 10 '12 at 9:17
Shouldn't that be $2^h-1$?
– Mike
Aug 10 '12 at 9:17
@Mike the number of internal nodes in a complete binary tree is 2^h-1 .
– Geek
Aug 10 '12 at 9:21
@Mike the number of internal nodes in a complete binary tree is 2^h-1 .
– Geek
Aug 10 '12 at 9:21
@Mike Yeah you are correct, actually i was thiking $theta(2^h)$; anyway corrected it
– pritam
Aug 10 '12 at 9:27
@Mike Yeah you are correct, actually i was thiking $theta(2^h)$; anyway corrected it
– pritam
Aug 10 '12 at 9:27
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f180974%2fexplanation-of-why-the-height-of-a-binary-tree-theta-lg-n%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
Hint: prove that a complete binary tree of hight $h$ has $2^h$ elements
– pritam
Aug 10 '12 at 9:03
@pritam thats a pretty good way of coming to this conclusion . Can you throw an answer so that I can accept it as the accepted answer .
– Geek
Aug 10 '12 at 9:11