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