0
$\begingroup$

In the naive matrix multiplication algorithm where you have 3 loops, the total number of multiplications is $n^2(n)=n^3$ given that we have two matrices each with size $n\times n$. But a proof claims that the number of additions is $(n-1)$, so the total number of additions is $n^2(n-1)$. I don't understand how the number of additions is $(n-1)$ as I think it should be $n$ because whenever we multiply we add that element, so we should have the same number of multiplications $n$?

$\endgroup$

1 Answer 1

2
$\begingroup$

When you add $n$ terms there are only $n-1$ additions. For example, $1+2+3$ has only two additions. You are making a fencepost error.

$\endgroup$
5
  • 1
    $\begingroup$ I wish I had found the name for this kind of error earlier! It crops up everywhere. $\endgroup$
    – Joe
    Jan 18, 2021 at 15:31
  • $\begingroup$ @Joe.Thank you very much, but why for boolean product, we would have $n$ or bit operations and not $n+1$ as in addition in traditional matrix multiplication in my question? $\endgroup$
    – Avv
    Jan 18, 2021 at 17:32
  • $\begingroup$ @Avra: I don't understand this question at all. What operation are you asking about? $\endgroup$ Jan 18, 2021 at 17:38
  • $\begingroup$ @RossMillikan. I mean the Boolean product of two matrices has two operations, meet $\cap$ and join $\cup$. The number of join operations, which are equivalent to addition in the above algorithm, is not $(n-1)$, but it's $n$ $\endgroup$
    – Avv
    Jan 19, 2021 at 14:31
  • $\begingroup$ I don't know what those operations are on matrices. I know what they are on sets, where there are $n-1$ operations on $n$ sets. $\endgroup$ Jan 19, 2021 at 15:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .