Derive the expression for the number of operations required to solve a system of n linear equations in n unknowns using the Gaussian Elimination Method. Assume that one operation refers to a multiplication followed by an addition.

GATE 1998 · Engineering Mathematics · System of Equations · medium

Answer: Total operations = n(n-1)(n+1)/3 + n(n-1)/2 = n(2n+5)(n-1)/6, approximately n^3/3 for large n.

1. Count forward elimination operations: At step k (k=1 to n-1), we have (n-k) rows to update; each row update requires (n-k+1) multiply-adds (n-k for coefficient matrix plus 1 for b-column). Cost at step k = (n-k)(n-k+1). Let j = n-k, so sum_{j=1}^{n-1} j(j+1) = sum j^2 + sum j = n(n-1)(2n-1)/6 + n(n-1)/2 = n(n-1)(2n-1)/6 + 3n(n-1)/6 = n(n-1)(2n+2)/6 = n(n-1)(n+1)/3.
2. Count back substitution operations: Solving x_n requires 0 multiply-adds (direct division), x_{n-1} requires 1, ..., x_1 requires (n-1). Total = 0 + 1 + ... + (n-1) = n(n-1)/2.
3. Compute total operations: Total = (n^3 - n)/3 + n(n-1)/2 = (2n^3 - 2n + 3n^2 - 3n)/6 = (2n^3 + 3n^2 - 5n)/6 = n(2n^2 + 3n - 5)/6 = n(2n+5)(n-1)/6. For large n this is approximately n^3/3.