Matrix multiplication verification So I have this ought to be simple example in my lecture notes but I just can't wrap my head around this guys solution. !Question I understand how there are $n$ multiplications but how are there $n$ additions for each element? Given a $3\times3$ multiplied by a $3\times3$ isn't the number of operations $45$, because there will be $\frac{2}{3}$ as many additions as multiplications so how is this equal to $2n^3$? I hope I'm not being crass. Thanks

Your reasoning is correct and the solution as written is wrong. The $-n^2$ summand is a lower-order term, though, and it is going to have only a very small impact for a matrix multiplication of order $n=1000$, so the estimation that you are asked to perform will be almost correct nevertheless.

The exercise is sloppily phrased and there are multiple issues with it; for instance:

1. Additional operations are needed in practice on a computer, for instance integer index bookkeeping.
2. As Pavel pointed out, the most natural implementation for a programmer is not the implementation with the minimum number of flops.
3. There are faster algorithms for multiplying matrices than the naive $O(n^3)$ method, although you are presumably not supposed to know this.



I personally would have avoided giving an exercise like this. It is very confusing.