What does an exact brute-force nearest-neighbour query cost in time and memory?
answer
- two factors, not one
- every stored row gets measured
- each distance costs d operations
- a size-k heap, not a full sort
- the training set is the model
basics
~20 sExact brute-force search compares the query against every stored point: O(nd) time per query for n stored points with d features each. Memory is the whole training set, all nd values plus their labels, held resident.
solid answer
~40 sAn exact search has to prove no point is closer, so it computes the distance from the query to all n stored points. Each distance touches d feature values, giving `O(n*d)` work per query; pulling out the k smallest costs another `O(n*log k)` with a size-k heap, which is almost never the bottleneck. Memory is the entire training set — there is no compressed model to fall back on. Storing 60,000 handwritten-digit images at 784 features each as 4-byte floats is 60000*784*4 bytes, about 188 MB, and doubles to roughly 376 MB in 8-byte precision. Both terms matter: doubling the rows and doubling the feature width each double the query cost, and in practice a wide scan is limited by how fast the rows stream out of memory, not by the arithmetic.
go deeper
Be ready to state O(n*d) per query out loud and say what n and d are. Also remember that the whole training set stays in memory, because there is no smaller fitted model to keep instead.
Explain why the selection step is O(nlog k) with a heap rather than O(nlog n) with a sort, and why the square root can be skipped when ranking. Be able to do the memory arithmetic for a concrete dataset size.
An interviewer expects you to move past asymptotics to what actually limits throughput: memory bandwidth, row layout and batching queries so the stored set is read once per batch rather than once per query.
Own the sizing decision: at what n and d does a resident exact scan stop fitting the latency and memory budget, and what does the organisation give up by keeping exactness versus by paying to shard the data across machines.
## What "exact" commits you to An *exact* nearest-neighbour query must return the truly closest stored point (or the truly closest k points) under the chosen distance function. That word is the whole cost story: to be certain nothing is closer, you must either measure every candidate or hold a proof that lets you skip some. Brute force takes the first route — it measures everything. ## The scan, step by step For a query vector `q` and a stored set of `n` points, each with `d` features: 1. For each stored row `x`, compute `dist(q, x)`. For Euclidean distance that is `sum over j of (q_j - x_j)^2`, i.e. `d` subtractions, `d` multiplications and `d` additions — `O(d)` per row. The final square root is monotonic, so ranking on the squared distance gives the same answer and the root is usually skipped. 2. Keep the best k seen so far. 3. Return them. Step 1 runs `n` times, so the query costs `O(n*d)`. That is the number every interviewer wants: **linear in the number of rows AND linear in the number of features**. Candidates who quote `O(n)` and drop the `d` are describing a one-dimensional dataset. ## The selection step Step 2 is often described as "sort the distances and take the first k", which would be `O(n*log n)`. You never need a full sort. A max-heap capped at size k gives `O(n*log k)`: push the first k distances, then for each remaining row compare against the heap's worst and replace only when the new distance is smaller. For any realistic k this term is dwarfed by the `n*d` distance work — with n = 2,000,000, d = 128 and k = 10, the distance arithmetic is on the order of 2.5 * 10^8 operations while the heap work is a few million cheap comparisons. ## The memory bill A brute-force neighbour search has no learned parameters to stand in for the data, so the stored set *is* the model and all of it must be reachable at query time. Storing 60,000 handwritten-digit images at 784 pixel features each: - as 4-byte floats: `60000 * 784 * 4` = 188,160,000 bytes, about 188 MB; - as 8-byte floats: about 376 MB; - plus one label per row, negligible by comparison. That fits comfortably in RAM. Ten million rows of 1,000 features at 4 bytes would be 40 GB and does not, which is when the design conversation starts: shard the rows across machines, keep the data on fast storage and accept the I/O, or reduce what you store. ## What actually limits throughput On modern hardware the per-row arithmetic is cheap and the *movement* of `n*d` values from memory into the processor is the real constraint. Two consequences follow. First, layout matters: rows stored contiguously so the scan reads memory in order run far faster than the same arithmetic over scattered objects. Second, batching matters: if 50 queries arrive within the same short window, scoring them in one pass over the stored set reads those `n*d` bytes once instead of 50 times, which is a large win for the same asymptotic complexity. ## Complexity of the other operations - Building the structure: `O(1)` — brute force stores the rows and does nothing else. - Inserting a new point: `O(d)` to copy it in; nothing to rebuild. - Deleting a point: `O(1)` amortised with a tombstone or a swap-with-last. - Querying: `O(n*d)`. That imbalance — trivial to update, expensive to query — is exactly the opposite profile from a structure that has to be built and rebuilt, and it is why brute force stays attractive for small or fast-changing collections. ## When brute force is the right answer It is not a fallback to be embarrassed about. It is the correct choice when the stored set is small enough that `n*d` fits your latency budget, when the data changes constantly and any index would be rebuilt continuously, when the feature space is wide enough that partitioning structures would degenerate to a full scan anyway, or when exactness is a hard requirement and you want an implementation with no parameters that can silently go wrong. A brute-force scan also serves as the ground-truth baseline against which any faster structure is checked. ## The two numbers to leave with Per query: `O(n*d)` time. Resident: `n*d` values. Every optimisation of exact search is an attempt to shrink one of those two products without changing the answer.
- Why is picking the k smallest distances rarely the bottleneck?Because a size-k heap does it in O(n*log k) using only cheap comparisons, while computing the distances themselves costs O(n*d) of arithmetic plus the memory traffic to read every stored value. With k in the tens and d in the hundreds, the distance pass dominates by orders of magnitude. Sorting all n distances would be wasteful; you only ever need the k best.
- How does the cost change when 50 queries arrive at once instead of one?Asymptotically it is 50 * O(n*d), but the constant improves a lot. Scoring the batch in a single pass reads the n*d stored values once rather than 50 times, and the arithmetic becomes one large block of multiply-adds instead of 50 thin ones. The per-query wall time drops even though the operation count does not.
- What in the stored set can you shrink without changing which neighbour is returned?Numeric precision and duplicates, mostly. Storing 4-byte instead of 8-byte values halves the bytes moved and almost never changes the ranking, and exact duplicate rows can be collapsed with a count. Dropping features shrinks d but changes the distance function itself, so the returned neighbour can change — that is a modelling decision, not a free optimisation.
It is a phone book with no alphabetical order: to be sure you have found the closest match you have to read every entry, and you have to keep the entire book on the desk.
saying these in an interview costs you the question
- Quotes O(n) and forgets the d factor in each distance
- Says the distances must be fully sorted to take the k smallest
- Claims only the k nearest points need to be kept in memory
- Assumes an index always removes the linear scan
- Confuses the cost of one query with the cost of a whole batch