# Runtime of Gaussian elimination/row reduction on an $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.

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.