How do various statistical techniques (regression, PCA, etc) scale with sample size and dimension? Is there a known general table of statistical techniques that explain how they scale with sample size and dimension? For example, a friend of mine told me the other day that the computation time of simply quick-sorting one dimensional data of size n goes as n*log(n).

So, for example, if we regress y against X where X is a d-dimensional variable, does it go as O(n^2*d)? How does it scale if I want to find the solution via exact Gauss-Markov solution vs numerical least squares with Newton method? Or simply getting the solution vs using significance tests?

I guess I more want a good source of answers (like a paper that summarizes the scaling of various statistical techniques) than a good answer here. Like, say, a list that includes the scaling of multiple regression, logistic regression, PCA, cox proportional hazard regression, K-means clustering, etc.
Most of the efficient (and non trivial) statistic algorithms are iterative in nature so that the worst case analysis O() is irrelevant as the worst case is 'it fails to converge'.

Nevertheless, when you have a lot of data, even the linear algorithms (O(n)) can be slow and you then need to focus on the constant 'hidden' behind the notation. For instance, computing the variance of a single variate is naively done scanning the data twice (once for computing an estimate of the mean, and then once to estimate the variance). But it also can be done in one pass.

For iterative algorithms, what is more important is convergence rate and number of parameters as a function of the data dimensionality, an element that greatly influences convergence. Many models/algorithm grow a number of parameters that is exponential with the number of variables (e.g. splines) while some other grow linearly (e.g. support vector machines, random forests, ...)