4.5-2 Professor Caesar wishes to develop a matrix-multiplication algorithm that

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 (n2) 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) + (n2). What is the largest integer value of a for which Professor Caesar's algorithm would be asymptotically faster than Strassen's algorithm?

Explanation / 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)=(n2). For the second case, with a=16, T(n)=(n2logn). In the first case of the master theorem, to be faster than Strassen, we need log4a<log27, which is a<72=49. Thus, the largest integer value will be 48.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.