Best, average and worst case

One algorithm, many costs

So far, step counts have been formulas in n alone. For many algorithms that is not enough, because the number of steps also depends on which input of size n they get. The trace above runs the same linear search on the same 8 elements four times: it needs 1, 4, 8 and 8 comparisons, depending only on the target.

So an algorithm doesn't have one cost; it has a range of costs. Three points in that range have names.

Best case

The best case is the fewest steps over all inputs of size n. For linear search it is 1, when the target sits at index 0.

On its own, the best case says little, since nearly every algorithm has some lucky input. It matters when the lucky input is common. Insertion sort, covered in the sorting module, takes O(n) steps on an array that is already sorted and only O(n²) on scrambled data. Real data is often nearly sorted, which is one reason real sorting routines use insertion sort for small or nearly ordered pieces.

Worst case

The worst case is the most steps over all inputs of size n. For linear search it is n: either the target is last, or it is missing and the search has to look everywhere to be sure.

The worst case is the default when people quote a complexity, because it is a guarantee: no input can make the algorithm slower. When you size a server, set a timeout or promise a response time, the guarantee is what you can rely on. Some algorithms with good average behavior have bad worst cases that are easy to trigger by accident:

• A quick sort that always picks the first element as its pivot takes O(n²) on input that is already sorted.
• A hash table whose keys all land in one slot degrades to a linear search.
• A binary search tree built from sorted keys becomes a long chain, and every operation becomes O(n).

Average case

The average case is the expected number of steps when inputs are drawn from some distribution. For linear search, if the target is present and every position is equally likely, the average is (1 + 2 + … + n) / n = (n + 1) / 2 comparisons, as the trace shows. That is half the worst case, but still O(n): averaging changed the constant, not the growth rate.

The catch is the assumption. "Every position equally likely" may be true of your data or not. When the assumption holds, the average describes what you will actually see, and it is why hash tables are said to be O(1): with a good hash function, keys spread evenly and a lookup checks a constant number of slots on average.

Randomized algorithms make a stronger kind of promise. A quick sort that picks its pivot at random takes O(n log n) expected steps on every input, because the averaging is over the algorithm's own coin flips, not over the inputs. No particular input is reliably bad, since the next run makes different choices.

When the worst case is an attack

An average-case assumption is about the inputs, and inputs often come from people you don't trust.

In 2011, researchers showed that the hash tables in most popular web frameworks could be flooded: send a request with thousands of parameters whose names all hash to the same slot, and the server spends seconds of CPU parsing one request. That is why Python, Ruby, Rust and Go now use hash functions with a random secret, as the hash tables module describes.

Regular expressions have the same problem. Some patterns, run by engines that backtrack, take exponential time on carefully chosen strings. In July 2019, one such pattern in a firewall rule pushed CPUs across Cloudflare's network to 100% and caused a global outage.

When inputs can be hostile, the worst case is the only number that matters.

Not to be confused: amortized cost

One more term sounds similar but means something else. Appending to a dynamic array is described as O(1) amortized. Most appends cost one step, and occasionally one copies the whole array, but the total over any sequence of n appends is O(n), so each costs O(1) on average over the sequence. No probability is involved: it is a guarantee about the total. The arrays module shows where the bound comes from, and the expert level covers how to prove such bounds.

Stating it precisely

In an interview or a design document, say which case you mean: "lookup is O(1) on average and O(n) in the worst case", "the algorithm is O(n log n) expected, with a randomized pivot", "appends are amortized O(1)". Each phrase makes a different promise, and the difference is exactly what the next question will probe.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Best, average and worst case from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

def find(a, target):
    for i in range(len(a)):
        if a[i] == target:
            return i
    return -1

#include <vector>
#include <algorithm>
 
long long processArrayInvariants(std::vector<int>& nums) {
    long long acc = 0;
    int lo = 0, hi = static_cast<int>(nums.size()) - 1;
    while (lo <= hi) {
        acc += nums[lo];
        if (lo < hi) acc += nums[hi];
        ++lo; --hi;
    }
    return acc;
}

public class ArrayInvariantSolver {
    public static long processArrayInvariants(int[] nums) {
        long acc = 0;
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            acc += nums[lo];
            if (lo < hi) acc += nums[hi];
            lo++; hi--;
        }
        return acc;
    }
}

def process_array_invariants(nums: list[int]) -> int:
    acc = 0
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        acc += nums[lo]
        if lo < hi:
            acc += nums[hi]
        lo += 1
        hi -= 1
    return acc

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.