The LOO Tax

You're comparing 5-fold cross-validation to leave-one-out cross-validation (LOO-CV) for a k-NN classifier that uses brute-force nearest-neighbor search over $n$ training points in $d$ dimensions. Which statement correctly describes the tradeoff?