Worst case and average case

The same operation has several honest costs, and it matters which one is being quoted.

How long is your commute? Most days, twenty-five minutes. On a bad day, when a train is cancelled, an hour and a half. Both answers are true, and which one you should quote depends entirely on why you are being asked. If it is idle conversation, say twenty-five. If you are deciding when to leave for a flight, twenty-five is a dangerous answer.

Costs in this course work the same way. When someone says an operation costs O(n), they might mean any of three different things, and the three are worth keeping apart.

• Worst case. The most it could ever cost, however unlucky you are. A guarantee.
• Average case. What it typically costs on ordinary data. An expectation.
• Amortised. The cost per operation across a long run, when occasional expensive operations are paid for by the many cheap ones. The next lesson is entirely about this one.

Counting all of them on one small example

Take a shelf of 100 books in no order, and you are searching for one specific title by checking spines from the left.

There is a fourth figure worth naming while we are here, though it is the least useful of them: the best case, meaning the least the operation could possibly cost if you are lucky. With that one added, all four can be counted on this shelf.

• Best case: it is the first book. 1 check.
• Worst case: it is the last book, or it is not on the shelf at all. 100 checks.
• Average case: it is equally likely to be in any position, so on average you check about half of them.

That average is worth doing properly rather than waving at. If the book is at position 1 you make 1 check, at position 2 you make 2, and so on up to 100. Add all of those and divide by 100.

The adding can be done in your head with one trick. Take the ends in pairs. 1 plus 100 is 101. 2 plus 99 is 101 again. 3 plus 98 is 101. Keep pairing inwards and you use up all hundred numbers in fifty pairs, each adding to 101. Fifty times 101 is 5,050. Divide that by the 100 positions and the average is 50.5 checks.

So the honest answers are: 1 check if lucky, 100 if not, about 50 typically. Notice that both 100 and 50.5 grow in proportion to the number of books, so both the worst case and the average case are O(n). Here the two agree on shape, and only differ by a factor of two. Sometimes they do not agree at all, and that is when the distinction earns its keep.

When worst and average part company

A hash table, later in this course, finds an item by computing where it should be rather than searching. Almost always this takes a constant number of steps regardless of size, so its average case is O(1). But it is possible for many items to be sent to the same place, and if every single item lands in the same place, a lookup degrades to checking all of them: O(n).

So a hash table is O(1) on average and O(n) in the worst case. Both numbers are true. Quoting only the first is normal and reasonable; forgetting the second is how people get surprised.