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
- worst case — The input of a given size that makes an algorithm do the most work, and the cost on that input.
- best case — The input of a given size that makes an algorithm do the least work, and the cost on that input.
- quicksort — A divide-and-conquer sort that picks a pivot, partitions the items into those smaller and larger than it, and sorts each part recursively.
Taught in
- Big O, Big Omega And Big Theta — Algorithms & Data Structures for Working Engineers
- Searching With Hashes Versus Trees — Algorithms & Data Structures for Working Engineers