# Computational complexity of Gaussian elimination

If it took me approximately 4 minutes to solve an equatian $Ax=b$ for $x$ (where $A$ is a $3\times3$ matrix and $b$ is a $3\times1$ matrix) using Gaussian elimination, how much longer would it take me to:

a) use Gaussian elimination to find $A^{-1}$ and then find $x=A^{-1}b$

b) if $A$ were a $30\times 30$ matrix and $b$ were a $30\times1$ matrix and I used Gaussian elimination to find $x$

c) if $A$ were a $30\times30$ matrix and $b$ were a $30\times1$ matrix and I used Gaussian elimination to find $A^{-1}$ and then find $x$ from $x=A^{-1}b$

I know there is an equation to use that helps you solve problems like this. I believe it is something like $(2/3)n^3$, but I am not sure how to use it, or even if that is the right equation.

• Do you mean by hand? Is this a practical question (in which case I think your psychology may significantly increase time in unpredictable ways) or a theoretical question about the complexity of Gaussian elimination? Sep 17 '13 at 19:57
• The time it takes to perform an algorithm is usually expressed in term of the number of arithmetic operations (additions and multiplications) that one needs to compute to complete the algorithm-- for Gaussian elimination see the corresponding wikipedia entry. As to how much actual time it takes you, well that depends on how quickly you can add and multiply ^^.
– jkn
Sep 17 '13 at 19:59
• Do you want complexity measured in the number of operations or in time considering the size of the operations? (Obviously, working with small numbers is faster than working with large numbers.) Sep 17 '13 at 20:18
• I am reffering to computational efficiency like jkn touched on. Assuming the time it takes me to do the arithmitic is constant, what would the new time be that it takes to do the algorithm. The correct equation is 2/3n^3 where n is the number of operations. Using gauss elimination I believe it took me 6 operations (3 for matrix reduction and 3 using back substitution but i am unsure if that is correct). If it did take me 6 operations to do that, then how many operations would it be to find the inverse and then find x using x = A^-1*b Sep 17 '13 at 21:14

This is not a full answer, but it is a partial one! It will take less than twice as much time to invert $A$ as to solve $Ax=b$ for $x$. The multiplication to get to $x$ will take time proportional to the square of the matrix size (that is, proportional to the number of elements in the matrix). So if you just need to solve the one equation, inverting is definitely a bad idea, but if you need to solve a lot with the same matrix, it might be reasonable, except that
1. If $A$ is not invertible, this will not work, and
2. If $A$ is a nasty old beast of a matrix that's just barely invertible, and you're calculating numerically, then this could give bad results.
In practice, better-behaved numerical methods are used to "decompose" $A$ into matrices that are faster to work with. I don't, however, remember any of them.