Successive Householder or Givens transformations produce full and reduced QR factorisations with the standard dense operation counts

For column $k$, apply [L2] to the subvector of rows $k$ through $m-1$. Embedding the resulting reflector or sequence of Givens transformations into the identity on the first $k$ rows leaves the earlier zeros unchanged and zeros all entries below the diagonal in column $k$. Repeating for $k=0,\dots ,n-1$ produces a unitary matrix $Q^{\ast }$ whose product with $A$ is upper trapezoidal; therefore $A=QR$ with $Q=(Q^{\ast }{)}^{\ast }$, and deleting the zero rows of $R$ gives the reduced factorisation, in the computational form refining the abstract QR existence of [L3].

In a dense real Householder step on the trailing block of size $(m-k)\times (n-k)$, forming the reflector costs $O(m-k)$ scalar operations and applying it to the trailing block costs $4(m-k)(n-k)$ scalar operations. Summing over $k=0,\dots ,n-1$ gives $4{\sum }_{k=0}^{n-1}(m-k)(n-k)+O\text{\hspace{0.17em}⁣}({\sum }_{k=0}^{n-1}(m-k))=2m{n}^2-\frac{2}{3}{n}^3+O(mn)\mathrm{.}$

In dense real Givens QR, column $k$ has $m-k-1$ entries to eliminate below the diagonal, and each rotation updates two rows across the remaining $n-k$ columns using $6(n-k)+O(1)$ scalar operations. Hence the cost is $6{\sum }_{k=0}^{n-1}(m-k-1)(n-k)+O(mn)=3m{n}^2-n^3+O(mn)\mathrm{.}$

Step 1.1 proves the constructive QR statement, and steps 2.1-2.2 give the standard dense operation counts.