Experimental studies have shown that the predictive accuracy of NN (nearest-neighbor) algorithms is comparable to that of the decision trees, rule learning systems, and neural net learning algorithms on many tasks. In addition, the probability of error of NN rules is bounded above by twice the optimal Bayes probability error. The theorems below show that NN algorithms can learn some concepts very efficiently using the best-case model. The teacher simply selects examples of the best possible locations in the n-dimensional features space, and provides these examples to the algorithm.