Worst Case, Average Case, Amortized Time Complexity: Three Guarantees, One Question

You tell an interviewer that ArrayList.append is O(1). They nod. Two minutes later they ask "what about worst case?" You say O(1) again. They write something on their rubric.

That note was not good.

Worst case, average case, and amortized are not synonyms or vague approximations of each other. They are different contracts. An interviewer who asks "which kind of O(1)?" is checking whether you know the difference, because mixing them up means you don't actually understand the algorithm you're describing.

Each makes a different promise. The math behind each one matters.

---

"O(1) time." Sure. Which kind?

---

One Question, Three Different Answers

People say "O(1)" like it's one thing. It isn't.

• Worst case asks: what is the maximum cost over all possible inputs of size n?
• Average case asks: what is the expected cost when inputs are drawn from some probability distribution?
• Amortized asks: what is the cost per operation when you spread the total cost over a long sequence, in the worst case?

That last phrase matters. Amortized analysis makes no probabilistic assumptions. It is a worst-case guarantee, just averaged over a sequence of operations rather than a single one. That's the distinction most people miss. They hear "average" and think "probably fast." Amortized means "provably fast on any sequence, ever."

---

Worst Case: The Hard Ceiling

Worst-case complexity is the one you use by default unless you have a reason not to. It's the tightest upper bound that holds for every possible input. No asterisks.

Binary search is O(log n) worst case because the search space halves at every step. An array of n elements takes at most ⌊log₂ n⌋ + 1 comparisons before you've either found the target or exhausted the range. The worst input is one where the target isn't there and the final comparison eliminates the last element. Nothing you feed into binary search can make it take more than log₂ n + 1 steps. Hand it to an adversary and they still can't break it.

Quicksort is the counterexample showing worst case can be terrible. With a naive last-element pivot strategy, a sorted input produces the worst possible partition: one side of size 0, the other of size n-1. The recurrence is:

T(n) = T(n-1) + T(0) + n = T(n-1) + n

Unrolling: T(n) = n + (n-1) + ... + 1 = n(n+1)/2 = O(n²).

Sorted array, last-element pivot. Every partition is maximally lopsided. This is why you shuffle first.

Worst case is what you reach for when designing a system that needs SLA guarantees, serving adversarial inputs, or running on a real-time control loop. If a spike at the wrong moment is unacceptable, the average case is irrelevant. Nobody's SLA says "we're fast on average."

---

Average Case: You Need a Model

Average case complexity is the expected running time when the input is drawn from some probability distribution. The words "on average" are hiding that probability model, and if your actual inputs don't match it, the guarantee breaks.

This sounds like a minor asterisk. It is not. More on that in a moment.

Quicksort's O(n log n) average case is typically proved over the uniform distribution on all n! permutations of n distinct elements. The elegant approach uses indicator random variables.

Define X_ij = 1 if elements of rank i and rank j are ever compared during the sort, 0 otherwise. By linearity of expectation, the expected number of comparisons is:

E[comparisons] = Σ_{i < j} Pr[X_ij = 1]

Elements i and j are compared exactly when one of them is chosen as pivot before any element with rank strictly between i and j. Among the j - i + 1 elements in the range [i, j], each is equally likely to be chosen first (uniform random pivot). So:

Pr[X_ij = 1] = 2 / (j - i + 1)

Summing over all pairs, with d = j - i ranging from 1 to n-1:

E[comparisons] = Σ_{d=1}^{n-1} (n - d) · 2/(d + 1)
               = 2(n+1)H_n - 4n
               ≈ 1.39 n log₂ n

where H_n = 1 + 1/2 + ... + 1/n is the n-th harmonic number. A clean O(n log n).

But notice what this required: a uniform distribution over random permutations. If an adversary controls your input, they hand you sorted data every time and the O(n²) worst case is exactly what you'll see.

The balanced version. Pretty. Holds only when inputs come from the right distribution.

This is not a hypothetical concern. The 2011 28C3 hash DoS attack exploited the average-case assumption in hash tables: by crafting 65,536 keys that all mapped to the same bucket, attackers turned O(1) average-case lookups into O(n) worst case and brought PHP and Python servers to their knees with a single HTTP request. One HTTP request. The kind of thing that makes you read the source code of your language runtime on a Friday night.

Average case is the right frame when your input distribution is genuinely random, or when you control the randomness yourself. Randomized quicksort shuffles the input before sorting, converting average case into expected case. That's a stronger guarantee: the coin flip belongs to the algorithm, not the adversary.

---

Amortized Time Complexity: No Probability, Just Accounting

Amortized analysis, introduced by Robert Tarjan in 1985, answers a different question. Amortized complexity is a worst-case bound on the average cost per operation over any sequence, with no assumptions about input distribution.

The dynamic array is the canonical example. It's also the reason ArrayList.append is O(1) amortized and not "just O(1)."

class DynamicArray:
    def __init__(self):
        self.data = [None]  # capacity starts at 1
        self.size = 0

    def append(self, val):
        if self.size == len(self.data):
            self._resize(2 * len(self.data))  # O(n) actual cost
        self.data[self.size] = val
        self.size += 1

    def _resize(self, new_cap):
        new_data = [None] * new_cap
        for i in range(self.size):
            new_data[i] = self.data[i]
        self.data = new_data

The worst-case cost for a single append is O(n), triggered when the array is full and must be copied. But that copy only happens at sizes 1, 2, 4, 8, ..., n/2. The total copy work for n appends is 1 + 2 + 4 + ... + n/2 = n - 1, plus n original writes, giving 2n - 1 total operations for n appends. Per-append cost: O(1).

This is amortized O(1). No probability. Even if an adversary designed the sequence of appends to cause as many resizes as possible, the math holds. You can't trick it.

Three Ways to Prove It

Tarjan's paper describes three methods. All three give the same result. Each is cleaner for different problems.

Aggregate method (what we just did): compute the total cost of n operations and divide by n. The dynamic array total is at most 2n - 1, so amortized O(1) per append.

Accounting method: charge each append 3 units of "credit" instead of 1. One unit pays for the current insert. One unit is saved on this element to pay for its eventual copy. One unit is saved on an old element (the one in the first half of the array that hasn't been prepaid yet). When resize happens, there's always enough credit saved to pay for it. Credit never goes negative. That invariant is the whole proof.

Potential method: define a potential function Φ on the data structure state, then compute amortized cost = actual cost + ΔΦ. For the dynamic array:

Φ = 2 · size - capacity

When size = capacity (full, about to resize): Φ = capacity. After resize, size = k+1, capacity = 2k: Φ = 2(k+1) - 2k = 2.

• No resize (size < capacity): actual cost = 1, ΔΦ = 2 (size grew by 1). Amortized = 1 + 2 = 3.
• Resize (size = k = capacity): actual cost = k + 1, ΔΦ = 2 - k. Amortized = (k+1) + (2-k) = 3.

Always 3, regardless of k. Amortized O(1).

The sawtooth. Every resize looks expensive but the function already saved up for it. Amortized cost stays flat at 3 the whole time.

The binary counter gives another clean aggregate proof. Incrementing an n-bit counter flips bit j once every 2^j increments. Total flips for n increments:

Σ_{j=0}^{∞} ⌊n / 2^j⌋  ≤  n · Σ_{j=0}^{∞} (1/2)^j  =  2n

O(1) amortized per increment, even though a single increment might flip all n bits.

---

The Confusion That Actually Costs You

Here's where the distinctions bite in interviews.

HashMap lookup is not simply "O(1)." Under the Simple Uniform Hashing Assumption (SUHA), the expected chain length at any bucket is α = n/m (load factor), so lookup is O(1) average case. But an adversary can craft keys that all hash to the same bucket, making every operation O(n) worst case. This is an average-case claim, not a worst-case claim. The rehashing that keeps α bounded is a separate amortized O(1) cost per insertion, the same doubling argument as the dynamic array.

Quicksort's O(n log n) is average case, O(n²) worst case, and amortized analysis doesn't really apply because quicksort is not a sequence-of-operations data structure. You can't "pre-pay" for a bad pivot on a future sort.

Union-Find with path compression and union by rank is O(α(n)) amortized per operation, where α is the inverse Ackermann function. This is not average case. It's a bound that holds for every possible sequence of union and find operations, regardless of the order you call them in.

The correct framing for each:

Data Structure / Algorithm	Claim	Correct Framing
ArrayList.append	O(1)	O(1) amortized, O(n) worst case
HashMap.get	O(1)	O(1) average case (SUHA), O(n) worst case
Quicksort	O(n log n)	O(n log n) average case (or expected, if randomized), O(n²) worst case
Binary search	O(log n)	O(log n) worst case
Union-Find (path compression)	O(1) per op	O(α(n)) amortized

---

How to Say It Precisely

Three rules:

• If the bound holds for every single input, say "O(f(n)) worst case" or just "O(f(n))."
• If it holds in expectation over random inputs or a randomized algorithm, say "O(f(n)) expected" or "O(f(n)) average case."
• If it requires spreading cost over a sequence, say "O(f(n)) amortized."

When you say "amortized" you're claiming a deterministic guarantee. When you say "average case" you're implicitly invoking a probability model. In an interview, stating the wrong type signals that you're recalling a fact rather than understanding it. Stating the right type, and knowing why, is what gets written as a positive signal.

Practicing that precision out loud is the thing that separates interview performance from solo LeetCode. SpaceComplexity runs voice mock interviews where the follow-up is exactly this: "what kind of O(1)?" Try it before a real interviewer does.

---

Recap

• Worst case: maximum cost over all inputs of size n. The default. Holds for every input, always.
• Average case: expected cost under a probability distribution over inputs. Requires specifying the model. Breaks if inputs don't match the assumption.
• Amortized: average cost per operation over any sequence, worst case. No probability. Distributes the cost of rare expensive operations over many cheap ones.
• Three methods for amortized proofs: aggregate (total / n), accounting (prepay with credits), potential (Φ function on state).
• HashMap is O(1) average case per lookup, O(n) worst case. ArrayList append is O(1) amortized, O(n) worst case. These are different guarantees.
• In interviews: say which kind you mean. It's a one-word addition that doubles the signal quality of your answer.

---

Further Reading

• Amortized analysis (Wikipedia)
• Tarjan, R.E. "Amortized Computational Complexity." SIAM Journal on Algebraic and Discrete Methods, 6(2):306-318, 1985
• Amortized Analysis, CLRS Chapter 17
• Average-case complexity (Wikipedia)
• Difference between average case and amortized analysis (GeeksforGeeks)