Example: Sorting
Example: Sorting
- It is difficult to quantify the number of vertices
- However, there must be at least one leaf for each possible re-ordering of keys
- There are n! possible reorderings
- The tree must have at least n! leaves
- A tree with k leaves must have height at least lg k
- lg(n!) Î Q(n lg n)