k-NN is a special case of a variable-bandwidth, kernel density "balloon" estimator with a uniform kernel [REF].
For multi-class k-NN classification, Cover and Hart (1967) prove an upper bound error rate of .