Best, average, worst

Written Explanation

A case is a kind of input

For an input size n, many inputs are possible. A case is a kind of input of that size:

• Best case: the luckiest input of size n, where the algorithm does the least work.
• Worst case: the unluckiest input of size n, where it does the most work.
• Average case: a typical input, averaged over the inputs you expect.

Each case has its own step count and so its own Big O. The case is a statement about the input, never about the machine or the programmer's luck.

Linear search

Take the array {7, 3, 9, 1}, with the search from BEG-017 counting one step per element read. I ran it for four targets:

target 7 index 0 steps 1
target 9 index 2 steps 3
target 1 index 3 steps 4
target 5 index -1 steps 4

• Best case: the target is the first element: 1 step, for any n. That is O(1).
• Worst case: the target is last or not present: n steps. That is O(n).
• Average case: if the target is present and equally likely to be anywhere, the average of 1, 2, 3, and 4 steps is 2.5, which matches (n + 1) / 2. It is about half of n, which is still O(n), because the half is a constant. The program printed average over present targets: 2.5.

The average case needs an assumption about which inputs are likely. Here: every position is equally likely. Change the assumption (for example, targets are usually at the front) and the average changes. That is why average-case claims always come with a stated assumption.

Binary search

For a sorted array of 8 elements {1, ..., 8}, counting one step per look:

target 4: 1 look   (the middle element, best case)
target 8: 4 looks  (the last element, worst case among present values)
target 0: 3 looks  (missing, smaller than everything)

Best case: O(1), when the first middle is the target. Worst case: O(log n), about log₂ n + 1 looks. Binary search is usually quoted as O(log n), the worst case.

Bubble sort with an early exit

BEG-017's bubble sort stops when a full pass makes no swap. Counting comparisons for n = 1,000:

bubble sorted input: 999, reversed: 499500

• Best case: the data is already sorted, so one pass of n - 1 = 999 comparisons finds no swap and the loop ends: O(n).
• Worst case: the data is in reverse order: n × (n - 1) / 2 = 499,500 comparisons: O(n²).

Notice that the best case of one algorithm (O(n)) can be a lot better than its worst (O(n²)).

Which case to quote

Usually the worst case, for three reasons:

1. It is a guarantee: no input of size n will cost more. That is what you need when you promise a response time.
2. It needs no assumption about what the inputs look like.
3. The best case is too optimistic to plan with. "It can be O(1)" says almost nothing if the usual case is O(n).

The average case is the right figure when the worst input is rare and you really do process many inputs: its value depends on the assumption you made. Always say which one you are quoting. Big O is a way of writing the growth; it does not mean "worst case". You can write the Big O of the best case, of the worst case, or of the average case.

When documentation says "average" or "amortized"

Two phrases you have already seen in the Java documentation:

• Average-case constant time. The HashSet and HashMap documentation promises constant-time basic operations assuming the hash function disperses the elements properly among the buckets. The HashMap page also warns that many keys with the same hashCode() is a sure way to slow a hash table down. So the constant-time figure is the average (typical) case under a good hash function; a bad hashCode can push a lookup toward the worst case. This is the same hashCode you wrote in BEG-026.
• Amortized constant time. The ArrayList documentation says add runs in amortized constant time: adding n elements takes O(n) in total. Occasionally an add takes longer, because (as I understand it, and the page I read does not spell this out) the list has to grow its internal storage and copy; spread over many adds, the average cost per add stays constant. "Amortized" means averaged over a sequence of operations, with no assumption about random input.

A third example: the Arrays.sort(Object[]) documentation says it needs far fewer than n lg n comparisons when the input is partially sorted, and about n comparisons for nearly sorted input. The best case is clearly better than the typical one.