seniorK-Nearest Neighbors
Why is KNN considered computationally expensive at inference time?
Updated May 16, 2026
Short answer
KNN requires computing distances to the entire training dataset at prediction time.
Deep explanation
Unlike parametric models, KNN stores all training data. For each query point, it computes distance to every stored point, making inference O(n × d). This becomes infeasible for large datasets without optimization structures like KD-trees or approximate nearest neighbor methods.
Real-world example
Image retrieval systems comparing query image to millions of stored embeddings.
Common mistakes
- Assuming KNN scales like logistic regression.
Follow-up questions
- What is the time complexity of KNN?
- Why is training fast?