Best, worst, and average case
Measure comparisons for lucky, unlucky, and typical inputs to the same algorithm.
On this page
Loops and linear search.
- Measure comparisons for lucky, unlucky, and typical inputs to the same algorithm.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
The running time of an algorithm often depends on which input of a given size it receives, not only on the size. The best case is the cheapest input of size n, the worst case is the most expensive, and the average case is the expected cost over a stated distribution of inputs. These describe the inputs; Big O, Ω, and Θ are notation that can describe any of them.
Linear search stops as soon as it finds the target. Searching for the first item costs one comparison, which is the best case. Searching for the last item, or for an item that is absent, costs n comparisons, the worst case. The average case needs a model: if the target is equally likely to be at each of the n positions, the expected number of comparisons is (1 + 2 + ... + n) / n = (n + 1) / 2.
Always state the model with an average-case claim. A different distribution, such as searches that mostly hit the front of a list, changes the answer. Worst-case bounds need no such assumption, which is why they are the usual guarantee for algorithms that must be predictable.
Code example
def comparisons(items, target):
count = 0
for item in items:
count += 1
if item == target:
break
return count
items = [10, 20, 30, 40, 50]
best = comparisons(items, 10)
worst = comparisons(items, 50)
miss = comparisons(items, 99)
average = sum(comparisons(items, value) for value in items) / len(items)
print(best, worst, miss)
print(average)
assert average == (len(items) + 1) / 21 5 5 3.0
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
def comparisons(items, target): count = 0 for item in items: count += 1 if item == target: break return count items = [10, 20, 30, 40, 50]best = comparisons(items, 10)worst = comparisons(items, 50)miss = comparisons(items, 99)average = sum(comparisons(items, value) for value in items) / len(items)print(best, worst, miss)print(average)assert average == (len(items) + 1) / 2Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Every item examined costs one comparison; the loop stops early when the target is found. | — | — | |
| The target is first, so one comparison is enough: the best case. | best = 1 | — | |
| The target is last, so all five items are examined: the worst case. | worst = 5 | — | |
| An absent target also costs n comparisons. | best = 1, worst = 5, miss = 5 | 1 5 5 | |
| Averaging over all five equally likely successful positions gives (n + 1) / 2 = 3. | average = 3.0 | 1 5 5 3.0 |
Behind the scenes
How Python processes this code
Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.
Cost and common mistakes
Linear search is O(1) in the best case, Θ(n) in the worst case, and Θ(n) on average: about n/2 comparisons for a uniformly placed present target.
- Do not equate Big O with the worst case, or Ω with the best case. Each case can be bounded above and below.
- An average-case result is only valid for the stated input distribution. Here it assumes a present target that is uniformly likely at every position.
- A best case such as O(1) is rarely a useful guarantee, because you cannot assume the input will be lucky.
Try it yourself
For a list of 9 distinct items, what is the average number of comparisons for a present, uniformly placed target?
Reveal answer and reasoning
(9 + 1) / 2 = 5 comparisons.