average case

The typical cost of an algorithm averaged over the inputs you expect, which requires a model of how inputs are distributed.

In more detail

Linear search for a target at a uniformly random position checks about half the list on average, which is still Theta(n). Quicksort is O(n log n) on average but O(n^2) in its worst case. The average depends on the assumed distribution, so it is a weaker promise than a worst-case bound.

Related terms

Taught in

References