1

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

Deepak
  • 26,801
Cameron
  • 13
  • The author is probably assuming the addition is $0 + A_{k,0}B_{0,j} + A_{k,1}B_{1,j} + \dots$, or in software something like "float sum = 0; for (int k = 1; k <= n; k++) { ... sum += ... }" which is why there are $n$ additions instead of $n-1$ additions. – DanielV Aug 10 '14 at 14:49

1 Answers1

1

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.

Federico Poloni
  • 3,465