Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In a least square regression algorithm, I have to do the following operations to compute regression coefficients:

  • Matrix multiplication, complexity: $O(C^2N)$
  • Matrix inversion, complexity: $O(C^3)$
  • Matrix multiplication, complexity: $O(C^2N)$
  • Matrix multiplication, complexity: $O(CN)$

How can I determine the overall computational complexity of this algorithm?

EDIT: I studied least square regression from the book Introduction to Data Mining by Pang Ning Tan. The explanation about linear least square regression is available in the appendix, where a solution by the use of normal equation is provided (something of the form $a=(X^TX)^{-1}X^Ty)$, which involves 3 matrix multiplications and 1 matrix inversion).

My goal is to determine the overall computational complexity of the algorithm. Above, I have listed the 4 operations needed to compute the regression coefficients with their own complexity. Based on this information, can we determine the overall complexity of the algorithm?


share|cite|improve this question
Could you expand further? You give three different measures of effort for matrix multiplication, and I'm not sure which is right. Also, there are at least three methods I know of for doing linear least squares (and a bit more for nonlinear least squares). What are you trying to do? Where did you get the algorithm you currently have? – J. M. Nov 22 '11 at 7:46
@J.M. I have provided more elaboration in my question. Please let me know if you need more information. – Andree Nov 22 '11 at 8:21
Okay... forming $\mathbf M=\mathbf X^\top\mathbf X$ is a matrix multiplication. Forming $\mathbf b=\mathbf X^\top \mathbf y$ is a matrix-vector multiplication. But, please, please, please, do not use inversion+multiplication to compute $\mathbf c=\mathbf M^{-1}\mathbf b$! It is better computational practice to form the Cholesky decomposition of $\mathbf M$ and use that in the computation of $\mathbf c$. – J. M. Nov 22 '11 at 8:28
Sure, thanks for the advice! However, I still need to know about how to determine the computational complexity of my current implementation. Can it be inferred from the information I provided above? – Andree Nov 22 '11 at 8:35
Actually, all I want to know is this: From the 4 matrix operations I listed above (with their own complexity), which one has the highest degree of complexity? 3 of them have the same degree of complexity, so I'm not sure which one that I can assign as the algorithm's overall complexity. – Andree Nov 22 '11 at 8:41
up vote 23 down vote accepted

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).

share|cite|improve this answer
Thanks for the answer Chris! I'm really impressed about how you notice that N > C, thus O(C^2N) dominates O(C^3). – Andree Nov 22 '11 at 8:50
Would it be possible to have a formal reference for OLS' computational complexity (an article, a textbook, or similar)? I would like to cite it in an academic paper. – Richard Hardy Jan 27 at 12:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.