When analyzing square matrix multiplication runtimes, I understand that the runtimes are
for the naive divide-and-conquer method, and
for Strassen's method.
Why is N divided by 2 and not 4?
How I understand it, the coefficient of (8 for naive, 7 for Strassen) is the number of recursions that each level introduces, or the growth rate of subproblems. The divisor is the factor of reduction of the problem. The addend is the runtime of each particular recurrence node.
If the naive algorithm and Strassen's method are both dividing the output matrix into matrices where is the number of rows and columns, isn't the problem being reduced by a factor of 4 and not 2, since at each level we are solving the problem for 4 smaller matrices?
Below is an image for the naive method that I obtained from GeeksforGeeks:
From Introduction to Algorithms, 3rd Edition, p. 77:
Let T(n) be the time to multiply two n x n matrices using this [the naive matrix multiplication] procedure.
n is not the number of elements in any one matrix, it is a dimension. So, since the matrix dimensions are recursively divided in halves, the divisor is 2 and not 4.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With