Average case(expected cost)

The work an algorithm takes over typical inputs rather than the hardest one. It needs an assumption about what typical means, so it is a weaker claim than a worst case bound. Quicksort is a common example.

• See also: Computational complexity
• See also: Worst case
• See also: Quicksort
• Used in: Measuring Work

Back to the glossary