# Can you beat the Strassen's Algorithm?

A Kaboobly Dooist 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.

If his algorithm creates $$a$$ subproblems, then the recurrence for the running time $$T(n)$$ becomes $T(n) = a\,T(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?

Details:

• If the running time of the Strassen's algorithm is $$T(n)$$, it satisfies the relation $T(n) = 7\, T(n/2) + \Theta (n^2)$

×