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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.