Exercise 6.6

In a 10-fold cross validation, suppose we have data folds as $D_1,\dots ,D_{10}$, each fold will have $\frac{N}{10}$ data points. For a given $k$ and a given fold $D_i$, for each point $x$ in $D_i$, we need compute its distance with all other points in $d$ dimension, which requires $O(\mathit{Nd})$ computations. We then need select the smallest $k$ distances, which requires $O(N\log <!--\; FUNCTION\; APPLICATION\; -->k)$ computations. So for each point in fold $D_i$, we need $O(\mathit{Nd}+N\log <!--\; FUNCTION\; APPLICATION\; -->k)$ computations.

We need to do the same for all $\frac{N}{10}$ points in fold $D_i$, so the total computation for a given fold is $O(\frac{N}{10}(\mathit{Nd}+N\log <!--\; FUNCTION\; APPLICATION\; -->k))$, with 10 folds, we have total cost of $O(N^{2}d+N^2\log <!--\; FUNCTION\; APPLICATION\; -->k)$ for a given $k$.

Now sum up over $k$, we have the total cost

The first term is approximately on the order of $O(N^{3}d)$

For the second term, we have

By Sterling approximation formula, we have

so

Then

Adding up with the first term, we have