# Run time complexity of nearest neighbor

A paper titled, "Efficient Neighbor Searching in Nonlinear Time Series Analysis (1996)" download link mentions that the time complexity for the naive NN approach is $$N^2/2$$ i.e., $$O(N^2/2)$$ where $$N$$ denotes the number of datapoints. I have attached a screenshot from the paper where this complexity is mentioned (second paragraph). However, in textbooks it is mentioned that the complexity of $$O(N)$$. I am a bit confused. Can somebody please help, what is the correct answer and why $$O(N^2/2)$$ is mentioned in the paper.

The paper mentions that the time complexity for the naive NN approach is $$𝑁^2/2$$ in order to argue for using non-naive algorithms that are faster for large $$N$$.
In fact, the paper goes on to say that $$O(N\log N)$$ is possible for arbitrary data distributions, using $$k$$-d trees and their variants and that $$O(N)$$ is possible for some data distributions.
My impression is that interest now is more in the dependence on dimension rather than on $$N$$.
• I mean the algorithm where you compute all $N\choose 2$ distances between pairs of points and pick the smallest ones. Dec 19 '20 at 1:59