Best, Worst & Average Case
Big-O is often misunderstood as "the complexity of an algorithm." In reality it only describes an upper bound — and that bound can be computed for three different scenarios: the best possible input, the worst possible input, and a typical random input. Understanding the distinction prevents a common mistake: dismissing a fast algorithm because it has a bad worst case, or trusting a slow algorithm because someone quoted its best case.
Definitions
Best case (Ω) — the input arrangement that makes the algorithm finish as fast as possible
Worst case (O) — the input arrangement that forces the algorithm to do the most work
Average case (Θ) — expected performance over all possible inputs, weighted by probability
Linear Search: A Concrete Walk-through
Linear search walks through an array from left to right looking for a target value. The same algorithm behaves very differently depending on where the target lives.
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i; // found — stop immediately
}
return -1; // not found
}
const arr = [3, 7, 1, 9, 4, 6, 2, 8, 5, 0]; // n = 10
// Best case: target is the FIRST element
linearSearch(arr, 3); // → 1 comparison, returns immediately. O(1)
// Worst case: target is the LAST element or not present
linearSearch(arr, 0); // → 10 comparisons
linearSearch(arr, 99); // → 10 comparisons (exhausts entire array)
// Average case: target is equally likely to be at any position
// Expected comparisons = (1 + 2 + 3 + ... + n) / n = (n+1)/2 ≈ n/2
// That is still O(n)Why Worst Case Is the Default
When someone says "linear search is O(n)" they mean the worst case. This is the industry default for a very practical reason: you cannot control what input your code receives in production.
If your algorithm processes user-uploaded files, database queries, or network packets, any of those could be the pathological worst case. A guarantee of "this will never take more than O(n) steps" is far more valuable than "this usually runs quickly."
The worst case is also the most straightforward to analyze — you just ask: what input maximizes the number of operations?
Average Case Probabilistic Analysis
Average case analysis assumes inputs are drawn from a probability distribution and computes the expected number of operations. For linear search on an array of n distinct elements where the target is present and equally likely to be at any position:
// Probability that target is at index i: 1/n // Operations if target is at index i: i + 1 comparisons // Expected comparisons = sum over i from 0 to n-1 of (1/n) * (i+1) // = (1/n) * (1 + 2 + 3 + ... + n) // = (1/n) * n(n+1)/2 // = (n+1)/2 // For n = 100: expected ~50.5 comparisons → O(n) average case // Same asymptotic class as worst case, just half the constant // If the target might NOT be present (probability p that it is present): // Expected comparisons = p * (n+1)/2 + (1-p) * n // Still O(n) regardless of p
The Three Cases for Binary Search
function binarySearch(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
// Best case: target is the MIDDLE element
// → 1 comparison, returns on the very first iteration. O(1)
// Worst case: target not present, or in the last position checked
// → log₂(n) iterations before search space is exhausted. O(log n)
// Average case: expected log₂(n) - 1 comparisons ≈ O(log n)
// Key insight: best and worst differ dramatically (O(1) vs O(log n))
// but both are much better than linear search's O(n) worst caseQuicksort: When Cases Diverge Dramatically
Quicksort is the most famous example of a case-sensitive algorithm. Its average and best cases are excellent, but a naive implementation has a catastrophic worst case.
// Naive quicksort — always picks the last element as pivot
function quickSort(arr, lo = 0, hi = arr.length - 1) {
if (lo >= hi) return arr;
const pivot = partition(arr, lo, hi); // Lomuto partition
quickSort(arr, lo, pivot - 1);
quickSort(arr, pivot + 1, hi);
return arr;
}
// Best case: pivot always lands exactly in the middle
// → log n levels of recursion, n work per level → O(n log n)
// Average case: random data, pivot splits roughly in the middle on average
// → O(n log n) expected — this is the typical real-world performance
// Worst case: array is already sorted (ascending or descending)
// → pivot always lands at one end, creating ONE subproblem of size n-1
// → n levels of recursion, n work per level → O(n²)
// This is why production sorts randomize the pivot!
const sortedArr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
// quickSort(sortedArr) → O(n²) with last-element pivot!Notation Summary
Notation | Meaning | Bound Type | Read as |
|---|---|---|---|
O(g(n)) | f(n) ≤ c·g(n) for large n | Upper bound | "at most" — worst case guarantee |
Ω(g(n)) | f(n) ≥ c·g(n) for large n | Lower bound | "at least" — best case floor |
Θ(g(n)) | both O and Ω apply | Tight bound | "exactly" — both bounds match |
o(g(n)) | strictly slower growth than g(n) | Strict upper | "strictly less than" |
Note that O, Ω, and Θ are notations — they can describe any of the three cases. It is correct to say "the best case is O(1)" (using O for an upper bound on the best case). The common convention of saying O for worst case and Ω for best case is just that: a convention, not a rule.
More Examples
Algorithm | Best Case | Average Case | Worst Case |
|---|---|---|---|
Linear search | O(1) | O(n) | O(n) |
Binary search | O(1) | O(log n) | O(log n) |
Insertion sort | O(n) — already sorted | O(n²) | O(n²) — reverse sorted |
Quicksort (naive) | O(n log n) | O(n log n) | O(n²) — sorted input |
Quicksort (random pivot) | O(n log n) | O(n log n) | O(n²) — astronomically rare |
Merge sort | O(n log n) | O(n log n) | O(n log n) |
Hash map lookup | O(1) | O(1) | O(n) — all keys collide |
Practical Interview Advice
// When asked "what is the complexity of your solution?" — give WORST case by default. // Then mention if best/average case differs significantly. // Example answer for a binary search: // "Time: O(log n) worst case — each iteration halves the search space. // Best case is O(1) if the target is the middle element on the first check. // Space: O(1) for the iterative version (no extra memory), // O(log n) for recursive version (call stack depth)." // Red flag: only quoting best case // "My sort is O(n) because it's fast when the array is sorted." // → An interviewer will immediately ask: "what about the average and worst case?"