structural:reformatting, stylistic:style_transfer, stylistic:tone
Computational complexity

The matrix multiplication algorithm that results from the definition requires, in the worst case, n 3 {\displaystyle n^{3}} multiplications and (n − 1) n 2 {\displaystyle (n-1)n^{2}} additions of scalars to compute the product of two square n × n matrices. Its computational complexity is therefore O (n 3) {\displaystyle O(n^{3})}, in a model of computation for which the scalar operations take constant time.

Rather surprisingly, this complexity is not optimal, as shown in 1969 by Volker Strassen, who provided an algorithm, now called Strassen's algorithm, with a complexity of O (n log 2 7) ≈ O (n 2.8074). {\displaystyle O(n^{\log _{2}7})\approx O(n^{2.8074}).} Strassen's algorithm can be parallelized to further improve the performance. As of January 2024, the best peer-reviewed matrix multiplication algorithm is by Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou and has complexity O (n). It is not known whether matrix multiplication can be performed in n time. This would be optimal, since one must read the n 2 {\displaystyle n^{2}} elements of a matrix in order to multiply it with another matrix.

Since matrix multiplication forms the basis for many algorithms, and many operations on matrices even have the same complexity as matrix multiplication (up to a multiplicative constant), the computational complexity of matrix multiplication appears throughout numerical linear algebra and theoretical computer science.