What is the time complexity of K-fold cross-validation? What is the time complexity of $K$-fold cross-validation? (linear in $K$, quadratic in $K$, cubic in $K$, exponential in $K$?)
My guess is linear in $K$, because each fold is evaluated once? $\mathcal{O}(K)$? (no pun intended).
 A: It's $O(n)$, where $n$ is your sample size, since you are going through your data $K$ times $O(Kn)$, but $K$ is just a constant. Each iteration you use $K-1$ folds for training and then you use the remaining fold to evaluate your model. So you are reading your whole data $K$ times.
But this is just for CV, not accounting for the models built on top of the folds.
If $K$ approaches $n$ (LOOCV) then the time complexity is actually $O(n^2)$.
A: *

*The usual and most general formulation of cross validation is embarassingly parallel. Computational time is approximately $k$ times the time to train the model on the whole data set. 
The time to train any such surrogate model may be sensitive to


*

*the numeber of cases actually in training ($\frac{k-1}{k}$th of the available cases)

*predicting the remaining $\frac{1}{k}$th of the cases

*the range of hyperparameters to consider.


The time complexity of these factors dependends entirely on the model that is undergoing the cross validation: Consider e.g. the hyperparameter grid. For certain models updating with a different hyperparameter set may be done in a fashion that saves large parts of the computation. E.g. in Principal Component Regression,  the time consuming step is typically the SVD ($O (n^3)$). Calculating results for varying numbers of retained components from one SVD is possible and often much faster than recalculating the SVD every time. Also this particular re-use of intermediate results is unproblematic in the sense that it doesn't introduce any particular risk of causing a data leak between testing and training.



*

*For the special case of $k = n$, i.e. leave-one-out cross validation and particular training algorithms, analytical expressions to calculate the LOO estimate are known. In that case, a whole lot of calculation may be saved.

*For further algorithms it may be possible to formulate model updates that calculate the effect of exchanging $\frac{1}{k-1}$ of the training cases and predicting them, also saving calculations.


The latter 2 approaches can IMHO be interesting when cross validation is employed during model training (e.g. for hyperparameter optimization). 
For verifcation/validation purposes on the other hand they are less useful as not only a "theoretical" performance is to be tested but the actual implementation of the training algorithm. Which means that the described calculational shortcuts should be avoided, the more so a logical error here may cause a data leak between training and test data.
