I've recently watched a video lecture on Strassen's recursive algorithm for multiplying 2 n x n matrices. The lecture also brought up the Master Method for computing the time complexity of this algorithm. However, when discussing the coefficient b - which from my understanding refers to the factor by which the subproblems decrease in size - it was assigned a value of 2.
My question is: since the 2 n x n matrices are recursively divided into 8 n/2 x n/2 matrices, why is the value of b 2 and not 4?
Thanks in advance!
The n in the complexity notation of O(n3) is the same as the n in n×n, so the complexity is expressed as a function of the size of one dimension of the matrices. Since that is halved through each recursion, b is 2.
You can see that the naive algorithm really goes through three nested loops of size n (the length of one row/column), not n×n (the size of the entire matrix), so this seems right.