What is the difference between time complexity and space complexity?

Time complexity describes how the amount of computation an algorithm needs grows as its input gets larger, while space complexity describes how the amount of memory it needs grows the same way, and HNSW is a good example of an algorithm where these two costs genuinely trade off against each other rather than simply moving together.

Why should time and memory usage be thought of as two separate costs rather than one combined measure of efficiency?

An algorithm’s overall resource footprint really involves two distinct kinds of cost: how long it takes to run, captured by time complexity, and how much memory it needs to hold while running, captured by space complexity, both typically described using Big-O notation, covered elsewhere in this glossary, to express how each one scales with input size. These two costs don’t automatically move together — an algorithm can be fast but memory-hungry, or memory-efficient but comparatively slow, and understanding them as separate concerns makes it possible to reason clearly about which trade-off actually matters most for a given situation, rather than treating “efficiency” as a single, undifferentiated quality.

How does this time-versus-space trade-off actually show up in HNSW’s own design choices?

HNSW‘s layered graph structure, covered throughout this site’s coverage of building the algorithm from scratch, spends extra memory storing multiple layers of connections for a fraction of its vectors specifically in order to reduce search time, since those extra layers are what let search jump across large distances quickly in the graph‘s upper layers before narrowing down in the denser bottom layer. This is a textbook example of trading space for time: the algorithm accepts a real, measurable increase in memory usage in exchange for a meaningful reduction in how much work a search actually needs to do, and this exact trade-off is why parameters like M, which controls how many connections each vector maintains, covered in this site’s tuning coverage, directly affect both the graph’s memory footprint and its search speed simultaneously, just in opposite directions.

Why does keeping this distinction in mind matter for anyone actually tuning or evaluating an HNSW index?

Reasoning about HNSW’s overall efficiency requires evaluating both time and space complexity together rather than optimizing one while ignoring the other, since a change that improves search speed, such as increasing the number of connections per vector, typically does so specifically by consuming more memory, and a change that reduces memory usage typically does so by giving up some amount of search speed in return. This is precisely why benchmarking practices covered elsewhere on this site emphasize recording both memory footprint and search latency together, rather than reporting either one in isolation, since a benchmark that only reports speed without also reporting the memory cost required to achieve it tells an incomplete story about how an index would actually behave under real resource constraints.

Recognizing time complexity and space complexity as genuinely separate, trading-off costs clarifies why tuning HNSW is fundamentally about finding the right balance between them rather than chasing either one in isolation. From here, the pages on Big-O notation and on the M parameter’s effect on graph structure show exactly where this trade-off gets applied concretely.