The decision tree has height at least $\log n!$

Question

The proof of the theorem

Any decision tree that sorts $n$ distinct elements has height at least $\log n!$

is the following:

Since the result of sorting $n$ elements can be any one of the $n!$ permutations of the input, there must be at least $n!$ leaves in the decision tree.

By the lemma:

A binary tree of height $h$ has at most $2^h$ leaves.

the height must be at least $\log n!$.

$$$$

At the lemma we have thast a binary tree of height $h$ has at most $2^{h}$ leaves, how do we get at the proof of the theorem at least ??

Answer 1

Because

A binary tree of height $h$ has at most $2^h$ leaves.

implies

A binary tree with at least $2^h$ leaves has a height at least $h$.

Answer 2

You need to distinguish $n!$ outcomes, and you need at least one leaf for each thing that you distinguish, so you need at least $n!$ leaves; this has nothing to do with the lemma. The lemma comes into play at the next step: if the height were less than $\lg n!$, the tree would have fewer than $n!$ leaves, so it must have height at least $\lg n!$.

Added: To see one reason that you might have more than $n!$ leaves, consider the following decision procedure for sorting three items, $a,b$, and $c$, by weight: weigh $a$ against $b$, then $a$ against $c$, and finally $b$ against $c$. Here’s half of the decision tree:

                                                                     / abc  
                                                                b<c /  
                                                            _______/  
                                                           /       \  
                                                      a<c /     c<b \  
                                                         /           \ acb  
                                         _______________/  
                                        /               \               
                                       /                 \           / impossible
                                      /               c<a \     b<c /  
                                     /                     \_______/  
                                a<b /                              \  
                                   /                            c<b \  
                                  /                                  \ cab  
                                 /  
                                 \  
                                  \ This will be the b<a side of the tree.  
                                    From the top down, it will have leaves 
                                    bac, impossible, bca, and cba.

In this case two of the leaves will never be reached, because they correspond to impossible situations, but they’re still part of the tree. (There are of course better sorting procedures!)