> In the limit that the size of your data goes to infinity, k-NN performs perfectly To be more precise, the result is that it is asymptotically no worse than t

> In the limit that the size of your data goes to infinity, k-NN performs perfectly To be more precise, the result is that it is asymptotically no worse than twice as bad as the best classification accuracy possible (the Bayes rate). KNNs have trivial training cost but, as you pointed out, have a non-trivial cost of generating a prediction. A related advantage that KNNs have is that it is easy to remove the effect of specific training examples from the model. With GDPR and other future legislations requiring the support of removing not only the user's data, but also the effect of the user's data from a trained model, KNNs are convenient.