Matrix Chain Ordering Problem (Matrix Chain Multiplication)

From Algorithm Wiki
Jump to navigation Jump to search


Matrix chain multiplication (or Matrix Chain Ordering Problem; MCOP) is an optimization problem. Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices.

Related Problems

Subproblem: Approximate MCOP

Related: Matrix Chain Scheduling Problem, Approximate MCSP


$n$: number of matrices

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Brute Force 1940 $O({4}^n)$ $O(n)$ Exact Deterministic
Dynamic Programming Algorithm (S. S. Godbole) 1953 $O(n^{3})$ $O(n^{2})$ Exact Deterministic Space
T. C. Hu ; M. T. Shing 1982 $O(n \log n)$ $O(n)$ Exact Deterministic Time

Time Complexity Graph

Matrix Chain Multiplication - Matrix Chain Ordering Problem - Time.png