What is the largest \(k\) such that if you can multiply \(3 \times 3\) matrices using \(k\) multiplications (not assuming commutativity of multiplication), then you can multiply \(n \times n\) matrices in time \(o(n^{\lg 7})\)? What would the running time of this algorithm be?
Strassens’s algorithm partitions the \(n \times n\) matrices into two \(n/2 \times n/2\) matrices, i.e. it divides the problem into sub-problems of size \(n/2\). But the algorithm in question asks for sub-problems of size \(n/3\) and in each recursive step it performs \(k\) matrix multiplications.
Hence, we can write the following recurrence for the running time:
\[T(n) = kT(n/3) + \Theta(n^2)\]Using case 1 of the Master theorem, the solution of this recurrence is \(T(n) = \Theta(n^{\log_3 k})\).
For \(T(n)\) to be \(o(n^{\lg 7})\), \(n^{\log_3 k}\) must be smaller than \(n^{\lg 7}\).
\[\begin{aligned} n^{\log_3 k} &< n^{\lg 7} \\ \log_3 k &< \lg 7 \\ k &< 3^{\lg 7} \approx 21.85 \end{aligned}\]Hence, the largest possible \(k\) is 21.
Running time of this algorithm would be \(T(n) = \Theta(n^{\log_3 21}) = \Theta(n^{2.77})\).