Average Case vs. Worst Case
Sometimes we will be interested in several performance values:
- Average Case: a random or average input
- Typical Case: it might typically be the case that the input
is ``nearly sorted''.
- Worst Case: to guarantee performance even
in the worst case of input data.
The worst-case figure gives the strongest guarantee,
and it may be easier to analyze.