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) \]

Problem Courtesy: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

×

Problem Loading...

Note Loading...

Set Loading...