Computational complexity of matrix multiplication: Difference between revisions

Revision as of 22:29, 25 May 2021

Revision as of 04:15, 28 May 2021

Line 273:

I(2^k) &\le 2I(2^{k-1}) + 6M(2^{k-1})+ 4 A(2^{k-1})\\

&\le 2^2I(2^{k-2}) + 6(M(2^{k-1})+2M(2^{k-2})) + 4(A(2^{k-1}) + 2A(2^{k-2}))\\

&\ldotsvdots

\end{align}</math>

If <math>M(n)\le cn^\omega,</math> and <math>\alpha=2^\omega\ge 4,</math> one gets eventually