Can you beat the Strassen's Algorithm?

Computer Science Level 5

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?



Problem Loading...

Note Loading...

Set Loading...