Cormen Edition 3 Exercise 4.5 Question 2 (Page No. 97)

Question

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 *n/4$,and the divide and combine steps together will take $\Theta(n^2)$ time. He needs to determine how many subproblems his algorithm has to create in order to beat Strassen’s algorithm. If his algorithm creates $a$ subproblems, then the recurrence for the running time $T(n)$ becomes $T(n)=aT(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?

Answer 1

Strassen's Matrix Multiplication Recurrence:

$T(n) = 7T(n/2) + n^{2}$ = $n^{\log_{2}7}$

 

Given $T(n)=aT(n/4)+Θ(n2)T(n)=aT(n/4)+Θ(n2)$ = $n^{\log_{4}a}$

For Professor Caesar’s algorithm to be asymptotically faster than Strassen’s algorithm

-> $n^{\log_{4}a}$ $<$  $n^{\log_{2}7}$

-> ${\log_{4}a}$ $<$  ${\log_{2}7}$

solving above equation we get $a$ $<$ $49$ , hence largest value of $a = 48$