I'm trying to determine the exact complexity of finding an $n\times n$ matrix inverse of $A$. If it is known that the complexity of Gaussian elimination is $\frac{2}{3}n^3 + \frac{1}{2}n^2+O(n)$, then is it true that the complexity of finding $A^{-1}$ should be about twice same, since we are effectively doing two sets of Gaussian eliminations in parallel plus some row interchanges and multiplications?
Please correct me if I'm wrong.
No, it's not true. You can use Gaussian elimination to invert a matrix in $O(n^3)$ time, but there are other algorithms that are even faster. The complexity of a problem is the running time of the fastest algorithm for that problem. Therefore, it is not correct that the complexity of matrix inversion is $\Theta(n^3)$.
See https://en.wikipedia.org/wiki/Gaussian_elimination#Computational_efficiency, https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm, https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra, https://scicomp.stackexchange.com/q/22105/4274, Complexity class of Matrix Inversion.
