Lower Bound Average Case

• Cannot be worse than worst case?(n lg n)

• Can it be better?

• To find average case, add up the lengths of all paths in the decision tree, and divide by the number of leaves.

Previous slide

Next slide

Back to first slide

View graphic version