Matrix Chain Multiplication in DSA Python - Time & Space Complexity

Time Complexity: Matrix Chain Multiplication

O(n³)

Understanding Time Complexity

Matrix Chain Multiplication finds the best way to multiply a chain of matrices with minimum cost.

We want to know how the time needed grows as the number of matrices increases.

Scenario Under Consideration

Analyze the time complexity of the following dynamic programming solution.

def matrix_chain_order(p):
    n = len(p) - 1
    m = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            m[i][j] = float('inf')
            for k in range(i, j):
                cost = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1]
                if cost < m[i][j]:
                    m[i][j] = cost
    return m[0][n-1]
    

This code finds the minimum number of scalar multiplications needed to multiply matrices in the best order.

Identify Repeating Operations

Look at the loops that repeat work:

• Primary operation: The innermost loop calculates cost for each split position k.
• How many times: The outer loops run over all matrix pairs and chain lengths, repeating the inner loop many times.

How Execution Grows With Input

As the number of matrices grows, the operations increase quickly because we check many pairs and splits.

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

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

Final Time Complexity

Time Complexity: O(n³)

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

Common Mistake

[X] Wrong: "Since we only have two loops, the time complexity is O(n²)."

[OK] Correct: There is actually a third nested loop inside, making the total work much larger than just two loops.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming solves complex problems efficiently, a key skill in many coding challenges.

Self-Check

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

Practice

1. What is the main goal of the Matrix Chain Multiplication problem?

easy

A. To find the maximum number of matrices that can be multiplied

B. To multiply all matrices in the chain directly without optimization

C. To count the total number of matrices in the chain

D. To find the minimum number of scalar multiplications needed to multiply a chain of matrices

Solution

1. Step 1: Understand the problem context

   The Matrix Chain Multiplication problem aims to multiply a sequence of matrices with the least cost in terms of scalar multiplications.

2. Step 2: Identify the goal

   The goal is to find the order of multiplication that minimizes the total number of scalar multiplications.

3. Final Answer:

   To find the minimum number of scalar multiplications needed to multiply a chain of matrices -> Option D

4. Quick Check:

   Minimum scalar multiplications = Goal [OK]

Hint: Focus on minimizing multiplication cost, not counting matrices [OK]

Common Mistakes:

• Thinking the goal is to multiply matrices directly without optimization
• Confusing the problem with counting matrices
• Assuming maximum multiplications is the goal

2. Which of the following is the correct way to initialize the DP table for Matrix Chain Multiplication in Python?

easy

A. dp = [[0 for _ in range(n)] for _ in range(n)]

B. dp = [0] * n

C. dp = [[0] * n]

D. dp = [0 for _ in range(n)]

Solution

1. Step 1: Understand DP table structure

   The DP table for Matrix Chain Multiplication is a 2D table of size n x n to store minimum costs for subproblems.

2. Step 2: Choose correct initialization

   dp = [[0 for _ in range(n)] for _ in range(n)] correctly creates a 2D list with zeros for all n rows and n columns.

3. Final Answer:

   dp = [[0 for _ in range(n)] for _ in range(n)] -> Option A

4. Quick Check:

   2D list initialization = dp with zeros [OK]

Hint: Use nested list comprehensions for 2D DP tables [OK]

Common Mistakes:

• Using one-dimensional list for 2D DP table
• Incorrectly initializing inner lists causing shared references
• Using single list instead of nested lists

3. What will be the output of the following code snippet for p = [10, 20, 30] representing matrix dimensions?

def matrix_chain_order(p):
    n = len(p) - 1
    dp = [[0]*n for _ in range(n)]
    for l in range(2, n+1):
        for i in range(n-l+1):
            j = i + l - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + p[i]*p[k+1]*p[j+1]
                if cost < dp[i][j]:
                    dp[i][j] = cost
    return dp[0][n-1]

print(matrix_chain_order(p))

medium

A. IndexError

B. 6000

C. None

D. 18000

Solution

1. Step 1: Trace the code execution

   p=[10,20,30], n=2, dp=[[0,0],[0,0]]. l=2, i=0, j=1, dp[0][1]=inf. k=0: cost=dp[0][0]+dp[1][1]+10*20*30=0+0+6000. However, the code tries to access p[j+1] = p[2], which is valid here (p has length 3). So no IndexError here.

2. Step 2: Confirm output

   Return dp[0][1] which is 6000.

3. Final Answer:

   6000 -> Option B

4. Quick Check:

   Cost = p[0]*p[1]*p[2] = 6000 [OK]

Hint: For chain of 2 matrices (n=2), cost is p[0]*p[1]*p[2] [OK]

Common Mistakes:

• Anticipating IndexError on p[j+1]
• Miscalculating cost (e.g., wrong indices)
• Forgetting single k split for l=2

4. Find the bug in this Matrix Chain Multiplication code snippet:

def matrix_chain_order(p):
    n = len(p) - 1
    dp = [[0]*n for _ in range(n)]
    for l in range(2, n+1):
        for i in range(n-l+1):
            j = i + l - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + p[i]*p[k]*p[j]
                if cost < dp[i][j]:
                    dp[i][j] = cost
    return dp[0][n-1]

medium

A. Return statement is missing

B. DP table initialization is wrong

C. Incorrect multiplication indices in cost calculation

D. Loop ranges are incorrect

Solution

1. Step 1: Review cost calculation formula

   The cost formula should be p[i] * p[k+1] * p[j+1], but code uses p[i] * p[k] * p[j], which is incorrect indexing.

2. Step 2: Identify correct indices

   Matrix dimensions are stored in p, so for multiplying matrices A_i..A_k and A_k+1..A_j, cost uses p[i], p[k+1], and p[j+1].

3. Final Answer:

   Incorrect multiplication indices in cost calculation -> Option C

4. Quick Check:

   Cost formula indices must be p[i], p[k+1], p[j+1] [OK]

Hint: Check dimension indices carefully in cost formula [OK]

Common Mistakes:

• Using p[k] instead of p[k+1]
• Mixing zero-based and one-based indexing
• Ignoring matrix dimension rules

5. Given matrices with dimensions p = [5, 10, 3, 12, 5, 50, 6], what is the minimum number of scalar multiplications needed to multiply the entire chain?

hard

A. 1510

B. 2010

C. 4050

D. 3500

Solution

1. Step 1: Understand the input and problem

   p has length 7, so there are 6 matrices with dimensions: 5x10, 10x3, 3x12, 12x5, 5x50, 50x6.

2. Step 2: Use dynamic programming to find minimum cost

   By applying the Matrix Chain Multiplication DP algorithm, the minimum cost is calculated as 1510 scalar multiplications.

3. Final Answer:

   1510 -> Option A

4. Quick Check:

   DP minimum scalar multiplications = 1510 [OK]

Hint: Use DP table to store subproblem costs for efficiency [OK]

Common Mistakes:

• Calculating cost manually without DP
• Mixing matrix dimensions incorrectly
• Forgetting to consider all parenthesization options