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?

This question is describing a form of the SQUARE-MATRIX-MULTIPLY-RECURSIVE algorithm that divides its input matrices into \(n/3 \times n/3\) submatrices. This new algorithm is represented by the following recurrence:

\[\begin{split} T(n) & = \Theta(1) + 27T(n/3) + \Theta(n^2) \\ & = 27T(n/3) + \Theta(n^2) \\ \end{split}\]

Supposing we can use a strategy similar to Strassen’s wherein we perform \(k\) multiplications instead of 27, we would instead be looking at the recurrence:

\[T(n) = kT(n/3) + \Theta(n^2)\]

Which we can solve using the 1st case of the master theorem. Let \(a = k\), \(b = 3\) and \(f(n) = n^2\). Then \(f(n) = O(n^{\log_3k-\epsilon})\) holds for \(0 < \epsilon \leq \log_3k - 2\) where \(\log_3k > 2\). Therefore \(T(n) = \Theta(n^{\log_3k})\).

Via trial and error with graphing, the largest \(k\) such that \(\log_3k < \log 7\) is \(21\).