Matrix multiplication
Computational complexity depends on parenthesization

Although the result of a sequence of matrix products does not depend on the order of operation (provided that the order of the matrices is not changed), the computational complexity may depend dramatically on this order.

For example, if A, B and C are matrices of respective sizes 10×30, 30×5, 5×60, computing (AB) C needs 10×30×5 + 10×5×60 = 4,500 multiplications, while computing A (BC) needs 30×5×60 + 10×30×60 = 27,000 multiplications.

Algorithms have been designed for choosing the best order of products; see Matrix chain multiplication. When the number n of matrices increases, it has been shown that the choice of the best order has a complexity of O (n log n). {\displaystyle O(n\log n).}
detectable_format:title, change_case:english_lowercase