How do various statistical techniques (regression, PCA, etc) scale with sample size and dimension?
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, ...)