worst case
The input of a given size that makes an algorithm do the most work, and the cost on that input.
In more detail
For linear search, the worst case is a target that is missing or sits at the end, so every element is checked. Worst-case bounds are guarantees: no input of that size can cost more. Attackers deliberately aim for worst cases, which is why hash flooding and sorted input to an unbalanced tree matter.
Related terms
- best case — The input of a given size that makes an algorithm do the least work, and the cost on that input.
- average case — The typical cost of an algorithm averaged over the inputs you expect, which requires a model of how inputs are distributed.
- big Theta notation — A way of writing an exact growth rate: Theta(f(n)) means the cost is both O(f(n)) and Omega(f(n)).
Taught in
- Why Complexity Matters In Production — Algorithms & Data Structures for Working Engineers
- Big O, Big Omega And Big Theta — Algorithms & Data Structures for Working Engineers
- Amortised Analysis: Why Append Is Cheap — Algorithms & Data Structures for Working Engineers
- Collisions In Practice And Hash Flooding — Algorithms & Data Structures for Working Engineers
- Comparison Sorts: Insertion, Merge And Quicksort — Algorithms & Data Structures for Working Engineers
- Binary Search Trees: Search, Insert And Delete — Algorithms & Data Structures for Working Engineers