What is the time complexity of the k-NN algorithm with naive search approach (no k-d tree or similars)?

I am interested in its time complexity considering also the hyperparameter k. I have found contradictory answers:

  1. O(nd + kn), where n is the cardinality of the training set and d the dimension of each sample. [1]

  2. O(ndk), where again n is the cardinality of the training set and d the dimension of each sample. [2]

[1] http://www.csd.uwo.ca/courses/CS9840a/Lecture2_knn.pdf (Pag. 18/20)

[2] http://www.cs.haifa.ac.il/~rita/ml_course/lectures/KNN.pdf (Pag. 18/31)

up vote 12 down vote accepted

Assuming $k$ is fixed (as both of the linked lectures do), then your algorithmic choices will determine whether your computation takes $O(nd+kn)$ runtime or $O(ndk)$ runtime.

First, let's consider a $O(nd+kn)$ runtime algorithm:

  • Initialize $selected_i = 0$ for all observations $i$ in the training set
  • For each training set observation $i$, compute $dist_i$, the distance from the new observation to training set observation $i$
  • For $j=1$ to $k$: Loop through all training set observations, selecting the index $i$ with the smallest $dist_i$ value and for which $selected_i=0$. Select this observation by setting $selected_i=1$.
  • Return the $k$ selected indices

Each distance computation requires $O(d)$ runtime, so the second step requires $O(nd)$ runtime. For each iterate in the third step, we perform $O(n)$ work by looping through the training set observations, so the step overall requires $O(nk)$ work. The first and fourth steps only require $O(n)$ work, so we get a $O(nd+kn)$ runtime.

Now, let's consider a $O(ndk)$ runtime algorithm:

  • Initialize $selected_i = 0$ for all observations $i$ in the training set
  • For $j=1$ to $k$: Loop through all training set observations and compute the distance $d$ between the selected training set observation and the new observation. Select the index $i$ with the smallest $d$ value for which $selected_i=0$. Select this observation by setting $selected_i=1$.
  • Return the $k$ selected indices

For each iterate in the second step, we compute the distance between the new observation and each training set observation, requiring $O(nd)$ work for an iteration and therefore $O(ndk)$ work overall.

The difference between the two algorithms is that the first precomputes and stores the distances (requiring $O(n)$ extra memory), while the second does not. However, given that we already store the entire training set, requiring $O(nd)$ memory, as well as the $selected$ vector, requiring $O(n)$ storage, the storage of the two algorithms is asymptotically the same. As a result, the better asymptotic runtime for $k > 1$ makes the first algorithm more attractive.

It's worth noting that it is possible to obtain an $O(nd)$ runtime using an algorithmic improvement:

  • For each training set observation $i$, compute $dist_i$, the distance from the new observation to training set observation $i$
  • Run the quickselect algorithm to compute the $k^{th}$ smallest distance in $O(n)$ runtime
  • Return all indices no larger than the computed $k^{th}$ smallest distance

This approach takes advantage of the fact that efficient approaches exist to find the $k^{th}$ smallest value in an unsorted array.

  • 1
    Great answer and I especially like the advice towards the use of quickselect. – usεr11852 Jun 19 '16 at 20:06
  • One more question: for the third option I believe that the time complexity should be O(nd+k), as you still have to compute the most common label among the k-nearest neighbors to emit a prediction, right? – Daniel López Jun 19 '16 at 21:05
  • @Daniel Since $k \leq n$, $O(nd+k)$ is the same as $O(nd)$. – josliber Jun 19 '16 at 21:07
  • Alright, thank you again, your answers have been of great help. – Daniel López Jun 19 '16 at 21:08
  • Last time I bother you: trying to determine the computational complexity of a modified version of k-NN I am working on, I get the following: O(nd+nd/p) Where by definition n, d and p are integers greater than zero. Can I simplify that to O(nd)? – Daniel López Jun 19 '16 at 21:23

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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