Why is efficency of Gaussian Elimination O(n^3)?

Question

Why is efficency of Gaussian Elimination $O(n^3)$? See Big O Notations.

Answer 1

Wikipedia states that it is $O(n^3)$ because it requires:

• $\frac{n(n+1)}{2}$ divisions
• $\frac{2n^3 + 3n^2 − 5n}{6}$ multiplications
• $\frac{2n^3 + 3n^2 − 5n}{6}$ substractions

i.e. an average of $\frac{2n^3}{3}$ operations. And the proof is in Farebrother, R.W. (1988), Linear Least Squares Computations, which I was not able to find for free on the internet.

So here is my interpretation of the result:

• $n$ equations with $n$ variables so it requires $n$ pivots -> $O(n)$
• for each pivot we substract a multiple of row from each other row - >$O(n^2)$
• Total runtime is $O(n^2 n) =O(n^3)$