Content deleted Content added
Add URL for Davie & Stothers paper, move quote to correct source. |
m →top: fix newline |
||
Line 9:
|volume=9|issue=3|pages=251
}}</ref> (see [[Big O notation]]).
This is an improvement over the naïve <math>\mathcal{O}(n^3)</math> time algorithm and the <math>\mathcal{O}(n^{2.807355})</math> time [[Strassen algorithm]]. Algorithms with better asymptotic running time than the Strassen algorithm are rarely used in practice, because the large constant factors in their running times make them impractical.<ref>{{citation
| last = Le Gall | first = F.
Line 16 ⟶ 17:
| pages = 514–523
| title = Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012)
| year = 2012}}.</ref> It is possible to improve the exponent further; however, the exponent must be at least 2 (because there are <math>n \times n = n^2</math> values in the result which must be computed).▼
▲It is possible to improve the exponent further; however, the exponent must be at least 2 (because there are <math>n \times n = n^2</math> values in the result which must be computed).
In 2010, Andrew Stothers gave an improvement to the algorithm, <math>\mathcal{O}(n^{2.374}).</math><ref>{{Citation
| |||