|
|
|
|
|
|
by MauranKilom
1913 days ago
|
|
|
> By definition, a matrix multiplication takes rows and multiplies them by columns. > you (by definition) need to multiply them by each other at least once Why does multiplying a row with a column require at least one multiplication? "By definition" it takes n multiplications (!), but in the context of matrix multiplication we can do it with less - possibly with O(1) multiplications. And it seems neither you nor me can come up with a good argument why it can't take less, despite discussing it for a while. Which is why "you need to write n² entries" is used as an argument for the O(n²) bound, even if it has nothing to do with the number of multiplications. |
|
|