Best Case, Worst Case, and the One You Get

Last timeReading the Cost Off the Work

The same procedure has three costs depending on what it is handed. Which of the three to plan around is a question about the situation, not about the code.

Every cost quoted so far has been a single number for a single procedure.

That was a simplification. Hand the same code two different inputs of the

same size and it can do wildly different amounts of work.

FIG 1Best, worst and typical for four familiar procedures

	best	worst	typical	gap between worst and ty
scanning a list for a va	1	3	3	1
insertion sort	3	5	5	1
simple quicksort	4	5	4	2
hash table lookup	1	3	1	3

The codes run constant, logarithmic, linear, linear times logarithmic, quadratic from one to five. The first two rows have a worst case on the same rung as the typical case, which makes them easy to reason about and easy to trust. The two marked rows are the dangerous ones: both are usually excellent and both have a worst case an entire rung worse, which is a gap that stays invisible in testing and then arrives in production on one particular input. The rest of the lesson is about that gap.

The one that is a promise

Of the three, only the worst case cannot be violated. Everything else is a

claim about luck or about data.

That matters in three situations. When there is a deadline, so that being slow

is a failure rather than an inconvenience. When the cost is paid by somebody

waiting. And when an outsider chooses the input, which turns the worst case

from an unlucky event into something anybody can request on demand.

FIG 2One procedure, four inputs of the same size

step	input to simple quicksort	comparisons on 10000 items	which case	why
1	random order	about 160 000	typical	each split lands near the middle
2	already sorted	about 50 000 000	worst	every split peels off one item
3	sorted backwards	about 50 000 000	worst	the same, from the other end
4	all values identical	about 50 000 000	worst	no split separates anything
5	random, with a random pivot	about 160 000	typical, reliably	the input no longer chooses the pivot

5 steps

Three of the four worst cases are inputs anybody would call ordinary, which is the point: already sorted data is the most common shape real data arrives in, and a column of identical values is what a status field looks like. The gap is a factor of three hundred at ten thousand items and grows with the input. The last row is the standard repair, and it is worth understanding as a change of who chooses: with a randomly chosen pivot the cost no longer depends on the input order, so an adversary who knows the code still cannot produce the worst case on demand.

The typical case and its assumption

An average is taken over a distribution of inputs, and the distribution is an

assumption that usually goes unstated.

The lesson stops here

1 more paragraph to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

Best Case, Worst Case, and the One You Get

The one that is a promise

The typical case and its assumption

1 more paragraph to go

This is the reading half

Read alongside