Matrix Chain Multiplication in DSA C - Time & Space Complexity

Time Complexity: Matrix Chain Multiplication

O(n³)

Understanding Time Complexity

We want to understand how the time needed to solve the matrix chain multiplication problem grows as we increase the number of matrices.

Specifically, how the number of calculations changes when we try to find the best way to multiply many matrices.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int matrixChainOrder(int p[], int n) {
    int m[n][n];
    for (int i = 1; i < n; i++)
        m[i][i] = 0;
    for (int L = 2; L < n; L++) {
        for (int i = 1; i <= n - L; i++) {
            int j = i + L - 1;
            m[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {
                int q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
                if (q < m[i][j])
                    m[i][j] = q;
            }
        }
    }
    return m[1][n-1];
}
    

This code finds the minimum number of scalar multiplications needed to multiply a chain of matrices by trying all possible ways to parenthesize the product.

Identify Repeating Operations

• Primary operation: The triple nested loops where the innermost loop tries all split points k between i and j.
• How many times: The outer loops run roughly n² times, and the innermost loop runs up to n times for each pair, making the main calculation repeat about n³ times.

How Execution Grows With Input

As the number of matrices n grows, the number of operations grows much faster because we check many ways to multiply them.

Input Size (n)	Approx. Operations
10	About 1,000
100	About 1,000,000
1000	About 1,000,000,000

Pattern observation: The operations grow roughly by the cube of n, so doubling n makes the work about eight times bigger.

Final Time Complexity

Time Complexity: O(n³)

This means the time needed grows very quickly as the number of matrices increases, roughly proportional to the cube of the number of matrices.

Common Mistake

[X] Wrong: "Since we use loops inside loops, the time complexity is just O(n²)."

[OK] Correct: There are actually three nested loops, so the innermost loop adds another factor of n, making it O(n³), not O(n²).

Interview Connect

Understanding this time complexity helps you explain why some problems need more time as input grows and shows you can analyze nested loops carefully.

Self-Check

"What if we used memoization with recursion instead of bottom-up loops? How would the time complexity change?"