Lower Bound Avg. III
Algorithms with balanced decision trees perform better, on the average than algorithms with unbalanced trees.
In a balanced tree with as few leaves as possible, there will be n! leaves and the path lengths will all be of length lg n!.
The average will be lg n!, which is ?(n lg n)