Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
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.
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.
