# Solved – QR decomposition computational efficiency

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?

Contents

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

Rate this post