Search code examples
algorithmrecursionmatrix-multiplicationdivide-and-conquer

Why is the input size divided by 2 and not 4 in the recurrence of square matrix multiplication?


When analyzing square matrix multiplication runtimes, I understand that the runtimes are

T(N) = 8T(N/2) + O(N^2)

for the naive divide-and-conquer method, and

T(N) = 7T(N/2) + O(N^2)

for Strassen's method.

Why is N divided by 2 and not 4?

How I understand it, the coefficient of T(N/2) (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 O(N^2) addend is the runtime of each particular recurrence node.

If the naive algorithm and Strassen's method are both dividing the output matrix into N/2 x N/2 matrices where N 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:

Naive method image


Solution

  • 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.