Question

4.5-2 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 x n/4, and the divide and combine steps together will take O(n) time. He needs to determine how many subproblems his algorithm has to create in order to beat Strassen’s algo- rithm. If his algorithm creates a subproblems, then the recurrence for the running time T(n) becomes T(n) = aT(n/4) + (n?). What is the largest integer value of a for which Professor Caesar's algorithm would be asymptotically faster than Strassen's algorithm?

Answer 1

ANSWER;

To fall in third case of the master theorem , we need to have a $<$16. In that case ,the algorithm will be

T (n) = $< \Theta$ (n 2). for the second case, with a= 16, T(n) = $< \Theta$(n 2 log n ) . In the first  case of the ,master theorem, to be faster than strassen, we need log 4 a $<$

log2 7, which is a $<$72=49 . thus, the largest integer value will be 48