I have a linear equation
$$Ax=b$$
where $A$ is non-singular matrix $N \times N$, $x,b$ are vector $N\times 1$, $A,b$ are given and I want to find $x$
It is clear that $x$ can find by $x=A^{-1}b$. I would like to know how computational complexity increasing when $N$ is increasing (you can use any method to find solution)? Thank you in advance
The exact methods for a $n \times n$ matrix need at least $n^2$ steps, the present theoretical boundary seems to be $O(n^{2.376})$ (source). Gauss elimination needs $O(n^3)$ (source).
There are approximative methods, like Gauss-Seidel which are faster.
And there are methods which have advantages for certain matrices.