Worst/best-case analysis compares an algorithm’s behavior across inputs of the same size. Worst-case analysis measures the greatest cost: for linear search, an absent value requires checking all N array elements. Best-case analysis measures the smallest cost: a value found in the first position ends the search immediately. section 1.3
Use the cases to reason about efficiency and tradeoffs:
- Treat the worst case as an upper bound and the best case as a lower bound for the algorithm. section 1.3
- Express time and space behavior with Big O notation, then examine how changing input size N changes the order of growth. section 1.3 section 1.5
- Prefer worst-case reasoning when edge cases can trigger system failures, while avoiding premature optimization or choosing an unsuitable implementation. section 1.3
Searching an array
For an array of N numbers, linear search has its best case when the target is first and its worst case when the target is last or absent. The worst case examines all N values, revealing how performance changes as the input grows. section 1.3
