Average-case analysis asks how long an algorithm usually takes across inputs, rather than focusing only on its fastest or slowest possible input. Big O notation can describe this typical performance alongside best-case and worst-case behavior. section 4.3 section 1.9
Quicksort’s average case
Quicksort touches O(n) elements at each level of its call stack. If the pivot divides the array reasonably evenly, the stack has O(log n) levels, giving O(n log n) time. Poor pivots can create O(n) levels and O(n²) time. Choosing a random pivot makes O(n log n) the average runtime, although an array containing only equal elements can still produce the worst case without additional logic. section 4.5 section 4.6
Use average-case analysis to keep several performance ideas separate:
- Worst-case analysis gives a guarantee about the slowest relevant input. section 1.9
- Best-case analysis describes especially favorable inputs, such as a pivot that splits an array evenly. section 4.5
- Average-case analysis explains why quicksort can be O(n log n) in practice even though its worst case is O(n²). section 4.5
Estimates based on a slow computer that performs 10 operations per second
Use the runtime estimates to compare how quickly common Big O classes grow; the numbers are illustrative rather than precise. section 4.3
