V. Pan has discovered a way of multiplying matrices using multiplications, a way of multiplying matrices using multiplications, and a way of multiplying matrices using multiplications. Which method yields the best asymptotic running time when used in a divide-and-conquer matrix-multiplication algorithm? How does it compare to Strassen’s algorithm?

We can extend the calculations we have done in previous exercise for sub-problems with multiplications as .

Hence, we need to find the minimum of the following:

Hence, the second method yields the best asymptotic running time when used in a divide-and-conquer matrix-multiplication algorithm.


This algorithm runs asymptotically faster than Strassen’s algorithm as .

If you have any question or suggestion or you have found any error in this solution, please leave a comment below.