The number of additions and multiplications involved in performing Gaussian elimination on any \(n \times n\) upper triangular matrix is of the order
Answer
(B)
Explanation
Gaussian elimination first creates zeros below the diagonal. For a full matrix this costs about \(\frac{2}{3}n^{3}\) additions and multiplications, the source of the \(O(n^{3})\) option. An upper triangular matrix already has those zeros, so this phase has nothing to do, and only back substitution remains:
\(x_{i} = \dfrac{1}{a_{ii}}\Big(b_{i} - \sum_{j \gt i} a_{ij}x_{j}\Big)\) for \(i = n, n - 1, \dots, 1\).
Row \(i\) needs \(n - i\) multiplications and \(n - i\) additions, so the total is \(\frac{n(n-1)}{2}\) of each: \(O(n^{2})\). \(O(n)\) is too small, because each of the roughly \(\frac{n^{2}}{2}\) entries above the diagonal is used once.
Answer: B