= Solution
For the small <QR decomposition>, each of the $k$ <Givens rotations> eliminates one subdiagonal entry of the <upper Hessenberg matrix>. At column $j$, apply the rotation to two rows in columns $j,\ldots,k$, costing $O(k-j+1)$ arithmetic operations. Summing gives $O(k^2)$, and applying the rotations to the right-hand side costs $O(k)$. <Backward substitution in a triangular system> costs $O(k^2)$.
Computing $\|b\|_2$ costs $O(n)$ and the final dense <matrix multiplication> $Q_ky_k$ costs $O(nk)$. Thus the total, with the <Arnoldi decomposition> already supplied, is
$$
O(k^2+nk+n)=\boxed{O(nk)},\qquad \boxed{s=1,\quad t=1}.
$$
Here $1\leq k<n$, since $Q_{k+1}$ has <orthonormal> columns in $\mathbb R^n$. In the standard dense arithmetic model, forming the general <matrix>–<vector> product gives the sharp $\Theta(nk)$ cost. The pair above records that two-parameter bound; looser bounds such as $O(n^2)$ are also possible because $k<n$. Treating $\widetilde H_k$ as an unstructured dense <matrix> would unnecessarily replace its $O(k^2)$ factorization by an $O(k^3)$ computation.
Back to article page
