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?

Brute-force nearest-neighbor search is $O(\log n)$ per query, so the number of CV folds barely affects total runtime

LOO-CV is far more expensive, requiring $n$ train/test splits (roughly $O(n^2 d)$ total for brute-force search) versus only 5 for 5-fold, but LOO gives an almost unbiased error estimate at the cost of higher variance across its $n$ scores

5-fold CV is always more expensive than LOO-CV because it retrains on larger folds each time

LOO-CV and 5-fold CV have identical computational cost since both evaluate every training point exactly once overall