Back to Study Material Data Structures and Algorithms

Best Average Worst Case

Every algorithm can be analyzed from three perspectives: the best case, the average case, and the worst case. Each reveals something different about how th...

Best Average Worst Case

Analyzing the Three Scenarios That Define an Algorithm's Behavior

Every algorithm can be analyzed from three perspectives: the best case, the average case, and the worst case. Each reveals something different about how the algorithm behaves and is useful in different contexts.

The best case is the input configuration that causes the algorithm to perform the fewest operations. It represents an optimistic scenario. For linear search, the best case occurs when the target element is the very first element in the array, requiring only one comparison. The best-case time is O(1). Best-case analysis is rarely the most useful measure because we cannot always guarantee favorable inputs.

The worst case is the input that maximizes the number of operations. It represents the performance guarantee: no matter what input you provide, the algorithm will not exceed this bound. For linear search, the worst case is when the target is the last element or not present at all, requiring n comparisons. Worst-case analysis, described using Big O, is the most common measure in software engineering because it provides a reliable upper bound on running time.

The average case represents the expected performance over all possible inputs, often assuming inputs are equally likely or follow some probability distribution. For linear search with a uniformly random target position, the expected number of comparisons is n divided by 2, which is still O(n) but with a smaller constant. Average-case analysis requires more mathematical machinery, typically probability theory, but gives a realistic picture of typical performance.

Quicksort is the classic example where these three cases diverge dramatically. The best case for quicksort occurs when each partition splits the array into two equal halves, giving O(n log n). The average case over random inputs is also O(n log n). The worst case occurs when every partition puts all elements on one side, for example when the pivot is always the smallest or largest element and the array is already sorted. This degrades to O(n^2). Randomizing pivot selection makes the worst case astronomically unlikely in practice.

Worked example: insertion sort has a best-case time of O(n) when the array is already sorted, because each element needs only one comparison to find its position. The worst case is O(n^2) when the array is reverse-sorted. For nearly sorted inputs, insertion sort is often faster than merge sort despite worse worst-case complexity.

Interview tip: when discussing sorting algorithms, mention all three cases. An algorithm with O(n^2) worst case but O(n) best case may be the right choice when your data is usually nearly sorted. Context always matters.