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.
