V. Pan has discovered a way of multiplying $$68 \times 68$$ matrices using $$132, 464$$ multiplications, a way of multiplying $$70 \times 70$$ matrices using $$143, 640$$ multiplications, and a way of multiplying $$72 \times 72$$ matrices using $$155, 424$$ 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 $$m$$ sub-problems with $$k$$ multiplications as $$T(n) = \Theta(n^{\log_m k})$$.

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

$\log_{68} 132,464 = 2.795128 \\ \log_{70} 143,640 = 2.795122 \\ \log_{72} 155,424 = 2.795147$

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 $$\lg 7 > 2.8 > \log_{70} 143,640$$.