# What is the computation time of LU-, Cholesky and QR-decomposition?

I found these information about computation-time of following decompositions:

1. Cholesky: (1/3)*n^3 + O(n^2) --> So computation-time is O(n^3)
2. LU: 2*(n^3/3) --> So computation-time is O(n^3) also (not sure)
3. QR: (2/3)*n^3 + n^2 + (1/3)*n- 2 --> So computation-time is O(n^3) as well

But what I found in other documents says that Cholesky is the fastest among these three algorithms, then comes LU, and last (slowest) is QR.

How we see here, in the formulas above? (or are my formulas wrong?)

• They are all cubic in asymptotic complexity, but Cholesky has the smallest coefficient, so in what sense is the statement about Cholesky being fastest in any sense problematic in this context? Commented Jul 4, 2018 at 14:55
• Oh okay I see. So the coefficient is relevant too. And in the case LU vs QR? They both have the same coefficient as well.. How is LU faster than QR? Commented Jul 4, 2018 at 15:18
• If you count all operations (namely $+,-,*,/$), then all algorithms are $\alpha n^3+O(n^2)$, where $\alpha=1/3$ for Cholesky, $\alpha=2/3$ for LU, and $\alpha=4/3$ for Householder. If you count only multiplication and division (which is usually much more expensive than addition or subtraction), the coefficients get halved. Commented Jul 4, 2018 at 17:18
• The coefficient is absolutely important in practice. Cubic means effort is 8 times larger when you double $n$, but whether is goes from 1 second to 8 seconds or from 1 hour to 8 hours is of course crucially important. Commented Jul 4, 2018 at 18:26
• Thank you for the explanation, both of Johan and Pavel! Commented Jul 4, 2018 at 18:41