Problem. You have n labelled training points in d dimensions. For a query point, find its k nearest training points (Euclidean distance) and predict the majority label among them. Do this for many queries.
train = (1, 1) A, (2, 1) A, (1, 2) A, (6, 5) B, (7, 7) B, (6, 7) B
query (2, 2), k = 3 → nearest: (2, 1), (1, 2), (1, 1) → A
query (6, 6), k = 3 → B
k-NN has no training step: all the work happens at query time, so the cost per query is the algorithm. Lesson 9.4 found the k closest points once; here the same selection runs for every query, which changes where the time goes.
ML context. k-NN is a strong baseline for classification on embeddings (label a new text by its nearest labelled neighbours), the core of retrieval-augmented generation (retrieve the k nearest chunks), duplicate detection, and evaluation of embedding quality (k-NN accuracy on held-out data). Each deployment eventually faces the same question: exact scan, or an index?