The same code, different luck
An algorithm does not have a single running time. Its cost depends on the specific input, so we describe behavior across a range of scenarios rather than one number.
Three classic cases
- Best case is the most favorable input, where the algorithm finishes with the least work. For a linear search this is finding the target in the first slot.
- Worst case is the most punishing input, where the algorithm does the maximum work. Linear search hits this when the target is absent.
- Average case describes typical behavior, computed by averaging cost over all expected inputs under some assumption about how likely each is.
Why worst case dominates
Engineers usually design around the worst case because it gives a guarantee that holds no matter what input arrives. Average case is informative but relies on assumptions about input distribution that may not match reality.
Best case can mislead
A flattering best case can hide poor typical behavior, so it is rarely the basis for a decision. Reporting only the best case is a common way to oversell an algorithm.
Key idea
Running time depends on the input, so we report best, average, and worst case, and we usually plan around the worst case because it is a hard guarantee.