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

\begin {aligned} n^{\lg \sqrt a} & < n^{\lg 7} \\ \lg \sqrt a & < \lg 7 \\ \sqrt a & < 7 \\ a & < 49 \\ \end {aligned}

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