The biggest optimization MathWorks have made in implementing nearest-neighbors search is that all the hard stuff is implemented in a MEX file, as compiled C, rather than MATLAB.
With an algorithm such as kNN that (in my limited understanding) is quite recursive and difficult to vectorize, that's likely to give such an improvement that the O() analysis will only be relevant at pretty high n
.
In more detail, under the hood the knnsearch
command uses createns
to create a NeighborSearcher
object. By default, when X
has less than 10 columns, this will be a KDTreeSearcher
object, and when X
has more than 10 columns it will be an ExhaustiveSearcher
object (both KDTreeSearcher
and ExhaustiveSearcher
are subclasses of NeighborSearcher
).
All objects of class NeighbourSearcher
have a method knnsearch
(which you would rarely call directly, using instead the convenience command knnsearch
rather than this method). The knnsearch
method of KDTreeSearcher
calls straight out to a MEX file for all the hard work. This lives in matlabroot\toolbox\stats\stats\@KDTreeSearcher\private\knnsearchmex.mexw64.
As far as I know, this MEX file performs pretty much the algorithm described in the paper by Friedman, Bentely, and Finkel referenced in the documentation page, with no structural changes. As the title of the paper suggests, this algorithm is O(log(n)) rather than O(n^2). Unfortunately, the contents of the MEX file are not available for inspection to confirm that.