What is expected-case complexity?

Expected-case complexity describes how an algorithm’s cost behaves on average when the algorithm’s own internal decisions involve randomness, which is a subtly different question from average-case complexity’s focus on the distribution of possible inputs, and the distinction matters directly for a randomized algorithm like HNSW.

How does expected-case complexity actually differ from average-case complexity, given how similar they sound?

Average-case complexity, covered elsewhere in this glossary, averages an algorithm’s cost across the range of inputs it might realistically encounter, treating the algorithm itself as behaving deterministically once a specific input is fixed. Expected-case complexity instead averages across the randomness the algorithm itself introduces internally, even when the input is held completely fixed — the same exact input can still produce different actual running times across different runs, purely because the algorithm makes different random choices each time it executes. These two sources of variability, the input and the algorithm’s own internal randomness, are conceptually distinct, and expected-case complexity is specifically the framing that addresses the second one.

Why is expected-case complexity the more precise way to describe HNSW’s behavior specifically?

HNSW‘s random level assignment, covered elsewhere in this glossary, means that even inserting the exact same fixed set of vectors can produce a structurally different graph from one build to the next, purely because of the algorithm’s own internal random draws rather than because of any difference in the input data itself. Because of this, claims about HNSW’s search performance, such as the logarithmic scaling covered in this site’s page on what can actually be proven about the algorithm’s complexity, are more precisely described as expected-case claims: they describe what happens on average across the algorithm’s own random construction choices, holding the underlying dataset itself fixed, rather than describing an average across different possible datasets the way average-case complexity would.

Does this distinction actually matter in practice, or is it mostly a technical formality?

The distinction matters most when reasoning carefully about where a performance guarantee’s uncertainty actually comes from: expected-case complexity says the uncertainty comes from the algorithm’s own randomness, meaning that repeating a build on the identical dataset can still yield somewhat different graph structures and performance, while average-case complexity would attribute variability to differences between datasets instead. For most everyday purposes, treating the two framings loosely as interchangeable rarely causes real confusion, but understanding the difference becomes genuinely useful when troubleshooting why two builds of the same exact dataset behave slightly differently, which is squarely an expected-case phenomenon tied to random level assignment rather than anything about the dataset itself.

Expected-case complexity pinpoints randomness inside the algorithm itself as the source of variability, distinguishing it clearly from average-case complexity’s focus on variability across different inputs. From here, the pages on average-case complexity and on random level assignment fill in the two ideas this distinction sits directly between.