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