Computational complexity of least square regression operation

For a least squares regression with $N$ training examples and $C$ features, it takes:

• $O(C^2N)$ to multiply $X^T$ by $X$
• $O(CN)$ to multiply $X^T$ by $Y$
• $O(C^3)$ to compute the LU (or Cholesky) factorization of $X^TX$ and use that to compute the product $(X^TX)^{-1} (X^TY)$

Asymptotically, $O(C^2N)$ dominates $O(CN)$ so we can forget the $O(CN)$ part.

Since you're using the normal equation I will assume that $N>C$ - otherwise the matrix $X^T X$ would be singular (and hence non-invertible), which means that $O(C^2N)$ asymptotically dominates $O(C^3)$.

Therefore the total time complexity is $O(C^2N)$. You should note that this is only the asymptotic complexity - in particular, for $C$, $N$ smallish you may find that computing the LU or Cholesky decomposition of $X^T X$ takes significantly longer than multiplying $X^T$ by $X$.

Edit: Note that if you have two datasets with the same features, labeled 1 and 2, and you have already computed $X_1^T X_1$, $X_1^TY_1$ and $X_2^TX_2$, $X_2^TY_2$ then training the combined dataset is only $O(C^3)$ since you just add the relevant matrices and vectors, and then solve a $C\times C$ linear system.

In particular this allows you do to very fast bootstrap, jackknife and cross-validation when you are training an OLS regression (or variants like ridge regression, lasso, constrained OLS etc).

I was confused at why the matrix multiplication was claimed to be $\mathcal{O}(C^2 N)$ here, which is $\mathcal{O}(N^3)$ when $N=C$, which is much slower than Strassen's $\mathcal{O}(N^{2.8})$ and Le Gall's $\mathcal{O}(N^{2.37})$.

It turns out that we are doing rectangular matrix multiplication where $N \ggg C$. There's much more data than variables.

There are algorithms with far better scaling than the naive $\mathcal{O}(C^2N)$ cost for the dominant part in Chris Taylor's answer.

You can multiply $X^TX$ with complexity $\mathcal{O}(C^{1.8}N)$ if using Strassen's $\mathcal{O}(C^{2.8})$ cost for $C \times C$ matrices, and in theory you can also do it with $\mathcal{O}(C^{1.37}N)$ if using the best known complexity for multiplication of $C \times C$ matrices (but keep in mind that Strassen's algorithm is often preferred because of the big constant in the latter algorithm).

I obtained this from the first equation of page 262 of this paper, by setting:

• $m=p=C$
• $n=N$
• $N > C$
• $\omega = 2.8$ for Strassen, and $2.37$ for the algorithm with best theoretical (but not practical) asymptotic cost.