Professor Caesar wishes to develop a matrix-multiplication algorithm that is asymptotically faster than Strassen’s algorithm. His algorithm will use the divide-and-conquer method, dividing each matrix into pieces of size $n/4 \times n/4$, and the divide and combine steps together will take $\Theta(n^2)$ time. He needs to determine how many subproblems his algorithm has to create in order to beat Strassen’s algorithm. If his algorithm creates $a$ subproblems, then the recurrence for the running time $T(n)$ becomes $T(n) = aT(n/4) + \Theta(n^2)$. What is the largest integer value of $a$ for which Professor Caesar’s algorithm would be asymptotically faster than Strassen’s algorithm?

Assymptotic running time for Strassen’s algorithm is $S(n) = \Theta(n^{\lg 7})$

Now, when $a$ increases, number of subproblems determines the assymptotic running time of the problem and case 1 of master theorem applies. So, in worst case, assymptotic running time of the algortihm will be $T(n) = \Theta(n^{\log_b a}) = \Theta(n^{\log_4 a}) = \Theta(n^{\log_2 \sqrt a})$

Now, for $T(n)$ to be smaller than $S(n)$, $n^{\lg \sqrt a}$ must be smaller than $n^{\lg 7}$.

Hence, largest integer value of $a$ is $48$.

If you have any question or suggestion or you have found any error in this solution, please leave a comment below.