Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

like image 269
L Lin Avatar asked Oct 18 '22 04:10

L Lin


1 Answers

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.

like image 197
cadaniluk Avatar answered Nov 15 '22 05:11

cadaniluk