Best, Worst, Average Complexity
When we analyze an algorithm, we care about how its performance changes with different kinds of input, not just its speed on one lucky run.
The same algorithm can be fast on one input and slow on another, so a single number rarely tells the whole story. This is why we describe performance using three cases: best, worst, and average.
Why We Need Multiple Cases
Consider searching for a number in a list.
- Sometimes you find it at the very first position.
- Sometimes it sits at the very end, or isn't there at all.
- Most of the time it's somewhere in between.
It's the same algorithm in every run, but the amount of work it does depends entirely on the input. To capture that range, we measure time complexity in three scenarios:
- Best case: the input that makes the algorithm do the least work.
- Worst case: the input that makes it do the most work.
- Average case: the work you'd expect on a typical input.
What They Mean
These three cases describe which input we are talking about. To describe how the running time grows for any one of those cases, we use asymptotic notation: O, Ω, and Θ.
It's worth separating the two ideas clearly, because they are often mixed up:
- Best, worst, and average pick the input scenario.
- O, Ω, and Θ put a bound on how the running time grows as the input gets large.
The three notations differ in the kind of bound they express:
- O(f(n)) is an upper bound. The running time grows no faster than
f(n). - Ω(f(n)) is a lower bound. The running time grows no slower than
f(n). - Θ(f(n)) is a tight bound. The running time grows exactly like
f(n), bounded above and below by it.
These two choices are independent, so you can apply any bound to any case. For example, linear search in the worst case is Θ(n): it grows no faster and no slower than n. In the best case it's Θ(1), because it finishes in a fixed number of steps. Θ here describes how tightly each case is bounded, it has nothing to do with the average.
In everyday practice, people most often state the worst case using Big O, because an upper bound on the worst case is a guarantee the algorithm will never exceed. That's a convention, not a rule. Big O can describe the best or average case too, and the worst case can be given as a tight Θ bound when we know it exactly.
Examples
Example 1: Linear Search
You have an array of n elements and need to find a given key by checking each element in order.
- Best case: the key is at the first position, so only 1 comparison is needed. Time complexity: O(1).
- Worst case: the key is at the last position or not present at all, so all n elements are checked. Time complexity: O(n).
- Average case: across all positions the key could be in, the search checks about n/2 elements on average, which is O(n) once we drop the constant.
Visualization
So overall: Best = O(1), Average = O(n), Worst = O(n).
Example 2: Binary Search
Binary search works on a sorted array and halves the search range on every step.
- Best case: the element is at the first midpoint we check, so only 1 comparison is needed. Time complexity: O(1).
- Worst case: the element is absent, so the search keeps halving the range until it is empty, going log₂n levels deep. Time complexity: O(log n).
- Average case: a typical search lands the element after roughly log n halvings. Time complexity: O(log n).
Visualization
So overall: Best = O(1), Average = O(log n), Worst = O(log n).
Example 3: Bubble Sort
Bubble sort repeatedly steps through the array, swapping adjacent elements that are out of order. The version below adds a swapped flag so it can stop early if a full pass makes no swaps.
- Best case: an already sorted array finishes in n−1 comparisons with no swaps, so the
swappedflag stays false and the algorithm exits after a single pass. Time complexity: O(n). - Worst case: a reverse sorted array forces a swap at every comparison, totalling (n−1)+(n−2)+...+1 = n(n−1)/2 operations. Time complexity: O(n²).
- Average case: a random input needs roughly half as many swaps as the worst case, but the comparisons still grow quadratically. Time complexity: O(n²).
Visualization
Putting the Three Examples Together
Here are all three algorithms side by side so the spread between cases is easy to compare.
Notice that bubble sort is the only one whose best case beats its worst case by a whole growth class, and that gap exists only because of the early-exit swapped flag. Without it, even a sorted array would run in O(n²).
Why We Usually Focus on the Worst Case
Of the three cases, the worst case is the one we lean on most when comparing algorithms or designing systems, usually stated as a Big O bound. Here's why.
1. It Gives a Guarantee You Can Rely On
The worst case is the most work an algorithm can ever do, regardless of the input. Stated as Big O, it becomes a ceiling: the running time will never grow faster than that bound.
If an algorithm is O(n log n) in the worst case, it will never grow faster than
n log n, even on the input that hurts it the most.
That ceiling is what you can build on. Systems with performance requirements, like databases, web servers, and real-time systems, are sized against the worst case, not the lucky case.
2. You Have to Plan for the Bad Inputs
In production, the inputs you didn't plan for are the ones that take you down. A search that's fast on most queries but quadratic on a pathological one will eventually meet that pathological one, often when load is highest. Sizing for the worst case is what keeps a system stable when traffic spikes or an adversarial input shows up.
3. The Average Case Needs a Distribution You Rarely Have
Average-case analysis assumes you know how inputs are distributed, and that assumption often doesn't hold. Real input distributions shift over time and are hard to pin down.
QuickSort averages O(n log n), but a poor pivot choice degrades it to O(n²). If your data happens to trigger that pattern, the average is cold comfort.
When you can't characterize the input distribution, the worst case is the safer thing to design around.
4. The Best Case Is Too Optimistic to Plan With
The best case tells you how fast an algorithm could run, not how fast it will run. Linear search finds the element in O(1) when it happens to be first, but that says nothing about a typical run. The best case is useful for intuition, not for comparison or capacity planning.
So far, we’ve looked at how algorithms behave in their best, worst, and average cases depending on the input they receive.
But sometimes the cost of an operation depends on when it happens, not just on the input. Some operations are cheap almost every time and expensive only once in a while, like inserting into a dynamic array that occasionally has to resize and copy everything.
Judged purely by its worst case, that resize looks slow. But spread across the many cheap insertions around it, the average cost per operation stays small.
To capture that longer-term view, we use amortized analysis.
In the next chapter, we’ll see how it evaluates algorithms where occasional expensive operations are paid off by many cheap ones, giving us a clearer picture of real performance over time.
Quiz
Best, Worst, and Average Complexity Quiz
10 quizzes