Number of bit operations in nxn zero-one matrix boolean product

1k Views Asked by At

I was reading transitivity closure from the book Discrete Mathematics and Its Application by Kenneth Rosen

It says that in the boolean product of nxn zero-one matrix, there are $n^2(2n-1)$ bit operations, however I am not able to understand how it came.

I thought, for calculating each entry of resultant product matrix, there will be n ANDings and (n-1) ORings. And there will be $n^2$ such entries in nxn product matrix. So that makes total of $n^3 (n-1)$ bit operations, then how it is also $n^2(2n-1)$?

1

There are 1 best solutions below

0
On BEST ANSWER

Your reasoning is correct, but your conclusion is not. You have $n^2$ elements, and you need $n$ ANDs and $n - 1$ ORs per element. Thus, in total, $\text{<# of elements>} \times \text{<ops per element>}$, or, $n^2 \cdot (n + n - 1) = n^2 \cdot (2n - 1)$.

Note that the same is true for "regular" multiplication as well. Of course, so long as everything is done naively.