What is average-case complexity?

Average-case complexity describes how an algorithm behaves on a typical input, averaged across the range of inputs it’s actually likely to encounter, which is a distinctly different question from the algorithm’s absolute worst possible behavior, and it’s the framing most relevant to understanding how HNSW performs on realistic, everyday datasets.

How does average-case complexity actually differ from the worst-case framing covered elsewhere in this glossary?

Worst-case complexity, covered elsewhere in this glossary, asks how an algorithm behaves on the single most unfavorable input imaginable, no matter how rare or contrived that input might be in practice. Average-case complexity instead asks how the algorithm behaves across the realistic distribution of inputs it’s actually expected to see, weighting typical, common inputs far more heavily than rare, pathological ones. An algorithm can have a poor worst-case complexity while still having an excellent average-case complexity, if the specific input that triggers that poor worst-case behavior almost never shows up in practice — this gap between the two framings is exactly why both are worth understanding separately rather than assuming one implies the other.

Why does average-case complexity matter so much specifically for understanding HNSW?

HNSW‘s performance is fundamentally shaped by randomized construction, covered elsewhere in this glossary as random level assignment, which means its behavior is naturally described in terms of what typically happens across many random outcomes rather than in terms of a single guaranteed bound that holds no matter what. Most of the widely cited claims about HNSW’s efficiency, such as search scaling logarithmically with dataset size, covered in this site’s page on what can actually be proven about the algorithm’s complexity, are fundamentally average-case or expected-case claims, describing how the algorithm behaves given the typical random outcomes its construction process produces, rather than describing a hard worst-case guarantee that holds under every conceivable circumstance.

Should someone evaluating HNSW for a real system rely primarily on average-case complexity, or look elsewhere too?

For the overwhelming majority of practical use cases, average-case complexity is genuinely the more useful and more relevant framing, since it reflects how the algorithm is actually going to behave the vast majority of the time on real, typical data. That said, any system with strict, non-negotiable requirements around worst-case latency or correctness needs to look beyond average-case complexity and reason explicitly about worst-case complexity as well, covered elsewhere in this glossary, since average-case guarantees say nothing about how badly, or how often, an unusual outlier input might perform.

Average-case complexity captures how an algorithm behaves under realistic, typical conditions, which is the framing most relevant to HNSW’s day-to-day behavior even though it isn’t the whole picture. From here, the pages on worst-case complexity and on the difference between expected value and worst case round out this glossary’s coverage of how to reason carefully about an algorithm’s guarantees.