# Can you beat the Strassen's Algorithm?

**Computer Science**Level 5

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

**Your answer seems reasonable.**Find out if you're right!

**That seems reasonable.**Find out if you're right!

Already have an account? Log in here.