k-NN computational complexity 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:


*

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

*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)
 A: 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.
