0
$\begingroup$

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.

image

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thank you for your answer....by naive NN do you mean the k nearest neighbor given here: sebastianraschka.com/pdf/lecture-notes/stat479fs18/… Can you please clarify this point? $\endgroup$
    – Sm1
    Dec 18 '20 at 15:00
  • $\begingroup$ I mean the algorithm where you compute all $N\choose 2$ distances between pairs of points and pick the smallest ones. $\endgroup$ Dec 19 '20 at 1:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.