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 2 $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:

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

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