The naïve way to multiply
runs in time O(n^3); for many years no one suspected this was less than optimal. But Strassen
discovered an algorithm which runs in time O(n^2.81...). This was very surprising
, and sparked new interest in matrix multiplication algorithm
s. Today the best known algorithm runs in time O(n^2.31...) (although with such a large constant factor that it is unclear if it is useful in the Real World
), but nothing is known about a lower bound
. In fact, it is not known that matrix multiplication cannot be done in O(n^2) (the size of the input).
The detailed algorithm is described in my writeup under matrix multiplication.