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$.