QR decomposition computational efficiency

Question

I am struggling to find a reference for this: In terms of big Oh notation does anyone know of any expressions for the computational time taken by commonly used algorithms for QR decompositions?

Answer 1

Wikipedia says the complexity is $O(n^3)$ floating point multiplication operations when using Householder reflections.

The following table gives the number of operations in the $k$-th step of the QR-decomposition by the Householder transformation, assuming a square matrix with size $n$.

$$\begin{array}{c|c|} \text{Operation} & \text{Number of operations in $k$th step} \\ \hline \text{Multiplications} & 2(n-k+1)^2 \\ \hline \text{Additions} & (n-k+1)^2 + (n-k+1)(n-k)+2 \\ \hline \text{Divisions} & 1 \\ \hline \text{Square Root} & 1 \\ \hline \end{array}$$

Summing these numbers over the $n-1$ steps (for a square matrix of size $n$), the complexity of the algorithm (in terms of floating point multiplications) is given by

$$ \frac{2}{3}n^3 + n^2+\frac{1}{3}n-2=O(n^3) $$

Surprisingly, I haven't found a complexity analysis for QR factorization stated in Golub & van Loan. Weird.