What is amortized analysis?

Amortized analysis measures an algorithm’s average cost per operation across a long sequence of operations, allowing an occasional expensive operation to be smoothed out and balanced against many cheaper ones, rather than judging every single operation in isolation by its own individual worst case.

Why would smoothing costs across a sequence of operations ever give a more honest picture than judging each operation on its own?

Some data structures have an occasional operation that’s genuinely expensive, surrounded by many other operations that are comparatively cheap, and if that occasional expensive operation is rare enough relative to how often it occurs, the total cost across a long sequence of operations still ends up quite reasonable on average, even though any single worst-case operation looked expensive in isolation. Judging every operation purely by its individual worst case would overstate how costly the data structure actually is to use over time, since it would treat that rare expensive operation as if it happened every single time rather than only occasionally. Amortized analysis corrects for this by spreading that occasional cost out across the whole sequence, producing a per-operation average that more honestly reflects real, sustained usage.

Where does this kind of reasoning show up concretely in HNSW’s own behavior?

Inserting a new vector into HNSW’s graph, covered throughout this site’s coverage of building the algorithm from scratch, typically costs roughly the same amount regardless of which vector is being inserted, since each insertion involves a similar amount of searching and connecting to nearby existing vectors, but the occasional vector that gets randomly assigned to an unusually high layer, covered in this glossary’s page on random level assignment, requires meaningfully more connection work than the ordinary case. Because high-layer assignments happen relatively rarely, thanks to the exponential distribution’s shape covered elsewhere in this glossary, this extra cost gets amortized across all of the far more common low-layer insertions, keeping the average cost per insertion reasonable even though any individual high-layer insertion looks disproportionately expensive if judged entirely on its own.

How does amortized analysis relate to the average-case and expected-case framings covered elsewhere in this glossary?

Average-case and expected-case complexity, both covered elsewhere in this glossary, describe how a single operation behaves on average across possible inputs or random outcomes, while amortized analysis instead describes how a sequence of many operations behaves on average across that entire sequence, which is a related but distinct question. A data structure can have an unusually expensive worst-case single operation while still having an excellent amortized cost per operation across a long sequence, precisely because amortized analysis is specifically designed to smooth out exactly this kind of occasional, rare expense rather than treating every operation as an isolated event.

Amortized analysis provides the right lens for understanding how a data structure performs under sustained, repeated use, rather than fixating on the cost of any single unusual operation in isolation. From here, the pages on random level assignment and on average-case complexity fill in the specific ideas amortized analysis draws directly from.