We then consider the convergence of the
k-nearest neighbor algorithm to a classifier making a fraction

of errors when examples are drawn from the uniform distribution on
S
n
, the unit sphere in
n dimensions, and classified according to a simple target function. We prove that if the target function is a single half space, then for
k appropriately chosen (
k
n/
2
ln(
–1)),
k nearest neighbor yields an

accurate classifier using a database of
M=
O(
n/
2
ln(
–1)) classified examples. However, when the target function is a union of two half spaces,
k nearest neighbor requires a number of examples exponential in
n to achieve high accuracy.