Is this computational complexity correct?

Question

Let

1. $\mathbf{A}\in\mathbb{R}^{n\times n}$
2. $\mathbf{B}\in\mathbb{R}^{n\times m}$
3. $\mathbf{x}\in\mathbb{R}^{m\times 1}$

If cost is being defined in terms of number of elementary opertions then what is the computational cost of following

\begin{equation} \mathbf{b}=\mathbf{A}^{-1}\mathbf{B}\mathbf{x} \end{equation}

My notes:

1. $\mathbf{Z}=\mathbf{A}^{-1}$ is $\mathcal{O}(n^3)$
2. $\mathbf{y}=\mathbf{B}\mathbf{x}$ is $\mathcal{O}(nm^2)$
3. $\mathbf{Z}^{}\mathbf{y}$ is $\mathcal{O}(n^2)$

Then is following correct

A. Total cost = $\mathcal{O}(n^2)+\mathcal{O}(nm^2)+\mathcal{O}(n^3)$

B. Entire operation is of $\mathcal{O}(n^3)$

Answer 1

You switched the complexity of 1. and 3.: computing $Z=A^{-1}$ by Gaussian elimination is $O(n^3)$, and multiplication of the matrix with a vector is $O(n^2)$. But the conclusion is correct if $m= O(n)$. Otherwise, $O(nm^2)$ can be bigger than $O(n^3)$, so it can be the main term in the sum.

In fact, there are faster ways of computing the inverse (at least, surely there are random algorithms) than the one provided by Gaussian elimination.