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

Question

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

Answer 1

Nick Higham's book "Functions of Matrices Theory and Computation" has a nice summary of the computation costs that he scraped from Golub and van Loan's "Matrix Computations" book that summarizes the constant costs. Do note, this all makes assumptions on how we want to value different operations, which are not all the same:

Anyway, it's easier to see why certain factorizations are faster than others.