best case
The input of a given size that makes an algorithm do the least work, and the cost on that input.
In more detail
Linear search's best case is finding the target in the first slot, costing one comparison. Best cases are rarely useful for planning, because you cannot count on getting them. They do explain why insertion sort is fast on nearly sorted input.
Related terms
- worst case — The input of a given size that makes an algorithm do the most 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.
Taught in
- Big O, Big Omega And Big Theta — Algorithms & Data Structures for Working Engineers
- Comparison Sorts: Insertion, Merge And Quicksort — Algorithms & Data Structures for Working Engineers