# Runtime of Gaussian elimination/row reduction on a rectangular $m \times n$ matrix

The runtime of Gaussian elimination on an $$n \times n$$ matrix is $$O(n^3)$$. What is the runtime on an $$m \times n$$ matrix?

I am taking Gaussian elimination to mean putting the matrix in reduced row echelon form. (Although I'm guessing there is no complexity difference between reduced row echelon form and just row echelon form.)

Surprisingly, I can't seem to find the answer anywhere online.

## 1 Answer

It is $$\Theta(mn\min(m,n))$$, big-times-small-squared.

To get the row echelon form, each step $$k=0,1,\dots,\min(m,n)-1$$ updates a $$(m-k)(n-k)$$ panel by doing $$O(m-k)(n-k)$$ operations. So in particular each step takes at most $$O(mn)$$ flops, and at least half of them require at least $$\frac{m}{2}\frac{n}{2}$$ operations. These two bounds allow you to conclude.

For the additional steps for the reduced REF, the analysis is similar, up to a factor 2 because of the zeros. Although for stability reasons you'd better stop at the REF and then rely on back-substitution.