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?

By applying the same technique as in Exercise 4.2-4 we are looking for the smallest value of the following:

\[\begin{split} n^{\log_{68}132,464} & = n^{2.7951284873614} \\ n^{\log_{70}143,640} & = n^{2.7951226897483} \\ n^{\log_{72}155,424} & = n^{2.7951473910934} \\ \end{split}\]

Therefore the fastest algorithm is the on that multiplies \(70 \times 70\) matrices in \(143,640\) multiplications. Since Strassen’s algorith runs in \(\Theta(n^{2.8073549220576})\) time, all three of these algorithms will outperform it.