Best, Average, Worst
Big-O describes the worst case, but the same code can be fast on friendly input. Insertion sort is O(n) on sorted input and O(n^2) on reversed input, with random input in between. Best, average and worst are three separate claims about one algorithm, and you should know which one you are quoting.
Insertion sort on 6 values that are already sorted. The code is the same every time. The cost is not: each element walks back past the larger values in front of it, and how far it walks depends entirely on the input.
Check your understanding
The player pauses before the one decision in this run and asks what happens next. Here it is, with the answer.
6 values, already sorted. How many comparisons will insertion sort make?
Answer: 5, one per element. Each element checks the one before it, sees it is not larger, and stops. n - 1 = 5.
How it runs, step by step
Insertion sort on 6 values that are already sorted. The code is the same every time. The cost is not: each element walks back past the larger values in front of it, and how far it walks depends entirely on the input.
Running insertion sort on 6 values arranged already sorted, counting comparisons.
Before running: the best case is n - 1 = 5 comparisons, one per element. The worst is n(n - 1) / 2 = 15, when every element walks past everything before it. Which will this input be?
Predict the number of comparisons before the sort runs. Best is 5, worst is 15.
Element 1, value 8: one comparison with 3, which is not larger, so it stays. Total 1.
Element 8 moves back 0 places. 1 comparisons so far.
Element 2, value 12: one comparison with 8, which is not larger, so it stays. Total 2.
Element 12 moves back 0 places. 2 comparisons so far.
Element 3, value 17: one comparison with 12, which is not larger, so it stays. Total 3.
Element 17 moves back 0 places. 3 comparisons so far.
Element 4, value 21: one comparison with 17, which is not larger, so it stays. Total 4.
Element 21 moves back 0 places. 4 comparisons so far.
Element 5, value 30: one comparison with 21, which is not larger, so it stays. Total 5.
Element 30 moves back 0 places. 5 comparisons so far.
5 comparisons and 0 swaps for 6 values: the best case. Best case is n - 1 = 5, worst is n(n - 1) / 2 = 15, average is about n squared over 4 = 9. Same code, O(n) or O(n squared) depending on the input, which is why each case is its own statement.
5 comparisons for 6 values, the best case. The best case is 5 and the worst is 15.
Remember
- Best, average and worst case are separate statements. O(n^2) worst does not mean slow on every input.
- Insertion sort: n - 1 comparisons on sorted input, n(n-1)/2 on reversed, about n^2/4 on random.
- Ask which case a bound describes before comparing two algorithms by it.
Topics covered
Related
Where this is used
Standard librariesTimsort in Python and Java
Python's list.sort and Java's Arrays.sort for objects use Timsort, which is designed around the best case rather than the worst. It scans for runs that are already in order and merges those, so input that arrives nearly sorted, such as log lines by timestamp or a list being re-sorted on a second key, costs close to n comparisons instead of n log n. The worst case stays O(n log n); the bet is that real input is rarely a random permutation.
SecurityHash flooding and SipHash
A hash table lookup is O(1) average and O(n) worst, and the worst case is simply many keys landing in one bucket. In 2011 researchers showed an attacker could choose form fields or JSON keys that all collide, turning one request into quadratic work and stalling PHP, Java, Python and Ruby servers. The fix was to stop assuming the input is random: Python 3.4 moved to SipHash with a per-process random seed, so an attacker cannot predict which keys collide.
DatabasesThe PostgreSQL query planner
The planner chooses between a nested loop, a hash join and a merge join by estimating the average cost under the statistics it holds about each table. A nested loop is the cheapest plan when the inner side returns two rows and the worst one available when it returns a million, so a stale row estimate does not make the query slightly slower, it selects the quadratic case. EXPLAIN ANALYZE prints estimated and actual row counts side by side exactly so you can see which case you got.
Web infrastructureCloudflare's 2019 regex outage
A backtracking regular expression engine is linear on most patterns and exponential on a few. On 2 July 2019 one new firewall rule containing the fragment .*(?:.*=.*) drove CPU to 100 percent across Cloudflare's network and took their traffic down for about half an hour. It passed testing because the average case was fine; the worst case only needs one input to find it. Go's regexp package and RE2 give up backreferences in exchange for a linear worst-case guarantee.
Why it works this way
If the worst case is O(n^2), why do libraries still ship quicksort?
Because the average case is what almost every real input gets, and quicksort's constants are small and its memory access is sequential. Libraries do not accept the bad worst case, they buy it off separately: libstdc++ runs introsort, which counts recursion depth and switches to heapsort past about 2 log n. The average stays quicksort's, the worst case becomes O(n log n).
Average over which inputs?
An average case only means something next to an assumed distribution of inputs, and the textbook assumption is that every permutation is equally likely. Real arrays are not: they are partly sorted, full of duplicates, or still in the order the last query returned them. The figure of about n^2/4 for insertion sort is the uniform-random number; on an almost-sorted log file the real count is near n. This is also how benchmarks mislead, since feeding sorted data measures the best case and reports it as the speed.
Average case is not the same as amortized
Average case is a probabilistic claim about one operation across a distribution of inputs. Amortized is a worst-case claim about a sequence of operations with no probability in it at all: n appends to a dynamic array cost O(n) in total whatever the input, so each is O(1) amortized. A hash lookup being O(1) average is the weaker promise, because badly chosen keys defeat it. And amortized O(1) still allows one single append to take O(n) when the array doubles, which matters when you care about one latency rather than a total.
Omega does not mean best case
O, Omega and Theta bound a function from above, from below and from both sides. Best, average and worst say which function you are bounding. They are two independent axes: insertion sort's worst case is Theta(n^2) and its best case is Theta(n), and it is equally true, if useless, that its worst case is O(n^3). Name the case first, then pick the bound.
Read more
- Best, worst and average caseWikipedia
- Amortized analysisWikipedia
- IntrosortWikipedia
- listsort.txt, the Timsort design notesCPython · github.com
- Details of the Cloudflare outage on July 2, 2019Cloudflare