Worst-case performance describes the most runtime an algorithm can require for inputs of a particular size. It provides a useful guarantee: the algorithm will not be slower than that bound. section 1.9
Searching a phone book
If you use simple search to find a name, you might succeed immediately. That is the best case. If the name is last—or absent—you inspect every entry, so the worst-case performance is O(n). section 1.9
Worst-case analysis does not describe every run. It deliberately focuses on the most demanding input arrangement, while average-case analysis describes typical behavior. section 1.9 section 4.5
Quicksort shows why the input arrangement matters:
- Choosing the first element as pivot for an already sorted array creates an empty sub-array at each step, producing O(n) call-stack levels and O(n²) runtime. section 4.5
- Choosing pivots that divide the array roughly in half creates O(log n) levels; each level touches O(n) elements, giving O(n log n) runtime. section 4.5
- Random pivots give quicksort O(n log n) average performance, although inputs containing only equal elements can still produce the worst case without additional logic. section 4.5
Estimates based on a slow computer that performs 10 operations per second
Compare estimated growth rates visually to see how worst-case bounds distinguish slower and faster algorithms. section 4.3
