Expected Cost, Amortized Cost, and Where the Average Comes From

Three statements that all sound like “this operation is cheap on average” are routinely used interchangeably. Amortized cost averages a deterministic quantity over a sequence of operations on one data structure. Expected cost averages over the random choices the algorithm itself makes. Average-case cost averages over a distribution of inputs, which is an assumption about the caller rather than a property of the algorithm. Only the first holds for every input sequence, and only the second survives an adversary who knows the input.

What each average is taken over

The potential argument for a dynamic array assigns each append an amortized cost of three units while the true cost of a few appends in the sequence is Θ(n). The averaging is over time: the credit that pays for a resize was deposited by earlier appends, and the bound holds for every sequence of operations, with no randomness anywhere. The sequence may be chosen adversarially, and the bound still holds, because it is a statement about a sum rather than about any single term. The construction of that argument is covered in dynamic arrays and amortized accounting.

A randomized quicksort with a uniformly random pivot performs 2n·ln n ≈ 1.386·n log₂ n comparisons in expectation. The averaging here is over the pivots the algorithm chooses, and the bound holds for every fixed input array, including one built by an adversary who cannot see the random choices. The worst case over pivots remains Θ(n²), and a run exceeds a constant multiple of the expectation only with a probability that decays as n grows, so the expectation alone is not a per-run guarantee.

An average-case bound over inputs requires a distribution over inputs. Stating that a hash table lookup is constant time on average, with the average taken over uniform random keys, asserts that keys arrive uniformly, which is rarely something a program can establish. The distribution has to be defended, and an adversary who knows it can choose keys that land in one bucket.

The three combine, and keeping the combination straight matters. An operation can be amortized O(1), expected O(1), both, or neither: a hash table with incremental resizing and universal hashing has expected amortized constant time per insertion, and neither half of that phrase may be dropped.

Randomizing the function rather than the input

Universal hashing removes the assumption about the input by moving the randomness into the data structure. A family of functions H mapping a universe U to {0, …, m−1} is universal if for any two distinct keys x, y, a uniformly chosen h ∈ H satisfies

Pr[h(x) = h(y)] ≤ c/m,   c a small constant

The classical construction takes a prime p larger than any key and forms h_{a,b}(x) = ((a·x + b) mod p) mod m for a ∈ [1, p−1] and b ∈ [0, p−1] uniform. A cheaper alternative is the truncated-product family: multiply the key by a uniformly random odd word and keep the high m bits, which collides with probability at most 2^(1−m). In both cases the probability is over the choice of function, and the bound holds for every pair of keys the adversary selects in advance, which is why the guarantee is stated per pair and not per input set.

Linearity of expectation converts the pairwise bound into a statement about the table. With n keys and m buckets, the expected number of colliding pairs is C(n, 2)·c/m ≈ n²/2m, which is the uniform-hashing rate up to the constant. Bucket contents under a random function behave like balls thrown into bins: with n keys and n buckets the expected length of the longest chain is about ln n / ln ln n, which for a million keys is around 5. The load factor α = n/m then controls the probe count. Under uniform hashing, an unsuccessful search examines 1/(1 − α) buckets and a successful search examines (1/α)·ln(1/(1 − α)): at α = 0.5 those are 2 and 1.39, at α = 0.75 they are 4 and 1.85, and at α = 0.9 they are 10 and 2.56.

def multiply_add_hash(a, b, p, m, x):
    """One member of the classical multiply-add-reduce universal family."""
    return ((a * x + b) % p) % m

def colliding_pairs(keys, a, b, p, m):
    buckets = {}
    for key in keys:
        buckets.setdefault(multiply_add_hash(a, b, p, m, key), []).append(key)
    return sum(len(v) * (len(v) - 1) // 2 for v in buckets.values())

Every pair of distinct keys contributes to the count with probability at most c/m, so the function above has expected value at most C(n, 2)·c/m when a and b are drawn uniformly and the keys are fixed first.

Deterministic hashing has no such guarantee, and the failure is total rather than gradual. If the function is fixed and known, an adversary can compute n keys that all map to one bucket, after which every operation costs Θ(n). Hashing in a library therefore either seeds the function from a per-process random source or uses a keyed family, so that the keys the adversary chose before the run are not the keys that collide during it.

How much independence the analysis needs

Pairwise independence bounds the collision count, and that is enough for chaining. Stronger properties are needed for other schemes, and the requirements are known exactly enough to be surprising. Open addressing with linear probing does not have its probe bounds covered by pairwise independence: for linear probing, five-wise independent hashing suffices and four-wise independence does not, so there are inputs on which the four-wise bound fails. Choosing a family that is k-wise independent for a modest k therefore matters when the probing scheme, not the bucketing, is being analysed, and the failure of low independence in an open-addressed table is a failure of the proof before it is a failure of the implementation.

Independence also governs what the adversary can do adaptively. An adversary who fixes the input before the hash function is chosen is defeated by any universal family. An adversary who observes the table’s occupancy and then chooses the next key requires the hash function to remain secret for the argument to survive, or requires the family to be independent enough that seeing occupancy does not predict the remaining hash values.

Why an amortized bound cannot rescue a single operation

The credit in an amortized argument belongs to the data structure’s history, not to the operation that needs it, and the distinction is visible whenever a caller can observe a single operation. A real-time loop that appends to a dynamic array will hit a resize at some iteration and take Θ(n), no matter how the sequence averages out. A hash table that rehashes everything when the load factor crosses a threshold has the same shape: the insertion that triggers the rehash is expensive, and the ones around it are cheap. Incremental resizing removes the spike by moving a constant number of entries per subsequent operation, at the price of keeping both tables alive and making lookups check two places. The amortized cost is unchanged, the worst case per operation drops from Θ(n) to Θ(1).

Expected bounds behave the other way. An expected O(1) hash lookup bounds each operation individually, since the probability is taken over the function, but it says nothing about a run of operations unless the random choices are independent across them or a concentration bound is available. Summing expectations across a sequence gives an expected total, which is the correct way to combine the two notions: the expected amortized cost of n insertions is the sum of the per-operation expectations, and tail bounds, not the expectation alone, are what turn that into a statement about what a given run will do.

Persistent data structures fall outside the amortized framework for a different reason. Credit deposited by an operation on one version cannot be spent by an operation on another version, because both versions may remain reachable and the earlier work is still needed in its original form. Bounds for purely functional structures are derived per operation, often with the expected-cost machinery of hashing or with a tree decomposition whose depth bounds the work, and the resulting guarantees are worst-case per update rather than amortized.

Choosing the right claim

A structure’s cost claim should name both the averaging and the adversary. Amortized O(1) per append, holding for any sequence: deterministic, sequence-level, no per-operation guarantee. Expected O(1) per lookup with a universal hash family, holding for any input chosen independently of the family: probabilistic, per-operation, and dependent on the family remaining secret. Average-case O(1) over uniformly distributed keys: a statement about the workload, not the algorithm. The word-RAM cost model fixes what a bucket access costs before any of these claims are meaningful, and the same machinery of randomization over structural choices reappears at a larger scale where even the cheapest analysis is adversarial and the only way to say anything is to bound what a perturbation of the input can do, as in smoothed analysis of the simplex method.