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

74 views
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?

edited

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$

## Related questions

1
41 views
Consider the regularity condition $af(n/b) \leq cf(n)$ for some constant $c<1$,which is part of case 3 of the master theorem. Give an example of constants $a\geq 1$ and $b>1$ and a function $f(n)$ that satisfies all the conditions in case 3 of the master theorem except the regularity condition.
Can the master method be applied to the recurrence $T(n)=4T(n/2)+n^2\ lg\ n$ ?Why or why not? Give an asymptotic upper bound for this recurrence.
Use the master method to show that the solution to the binary-search recurrence $T(n)=T(n/2) + \Theta(1)$ is $T(n)=\Theta(lg\ n)$.
Show that if $f(n)=\Theta(n^{log_ba}\lg^kn )$, where $k\geq0$ then the master recurrence has solution $T(n) =\Theta(n^{log_ba} \lg^{k+1}n)$.For simplicity, confine your analysis to exact powers of $b$.