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\).