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?"

Practice

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

easy

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

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

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

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

Solution

1. Step 1: Understand the problem objective

   The Matrix Chain Multiplication problem aims to find the best way to multiply matrices so that the total number of scalar multiplications is minimized.

2. Step 2: Identify the correct goal

   Among the options, only To find the minimum number of scalar multiplications needed to multiply a chain of matrices describes minimizing scalar multiplications, which is the main goal.

3. Final Answer:

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

4. Quick Check:

   Goal = minimize multiplications [OK]

Hint: Remember: minimize multiplication cost, not count matrices [OK]

Common Mistakes:

• Thinking the goal is to multiply matrices directly without optimization
• Confusing counting matrices with minimizing operations
• Assuming maximum matrices multiplication is the goal

2. Which of the following is the correct way to declare the dimensions array p for 4 matrices with dimensions 10x20, 20x30, 30x40, and 40x50 in C?

easy

A. int p[5] = {10, 20, 30, 40};

B. int p[4] = {10, 20, 30, 40};

C. int p[4] = {10, 20, 30, 40, 50};

D. int p[5] = {10, 20, 30, 40, 50};

Solution

1. Step 1: Understand the dimensions array size

   For n matrices, the dimensions array size is n+1. Here, 4 matrices need an array of size 5.

2. Step 2: Check the array values

   The array should list the row count of the first matrix and then the column counts of each matrix in order: {10, 20, 30, 40, 50}.

3. Final Answer:

   int p[5] = {10, 20, 30, 40, 50}; -> Option D

4. Quick Check:

   Array size = matrices + 1, values match dimensions [OK]

Hint: Dimensions array length = number of matrices + 1 [OK]

Common Mistakes:

• Using array size equal to number of matrices instead of number + 1
• Missing the last dimension in the array
• Including extra or fewer elements than needed

3. What is the output of the following C code snippet for Matrix Chain Multiplication cost calculation?

int p[] = {5, 10, 3, 12, 5};
int n = 4;
int m[5][5] = {0};

for (int L = 2; L <= n; L++) {
    for (int i = 1; i <= n - L + 1; i++) {
        int j = i + L - 1;
        m[i][j] = 1000000;
        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;
        }
    }
}
printf("%d", m[1][n]);

medium

A. 201

B. 405

C. 270

D. 150

Solution

1. Step 1: Understand the matrix dimensions and initialization

   p = {5,10,3,12,5} means matrices: 5x10, 10x3, 3x12, 12x5. The code calculates minimum multiplication cost using dynamic programming.

2. Step 2: Calculate minimum cost m[1][4]

   Calculations:
   - m[1][2] = 5*10*3 = 150
   - m[2][3] = 10*3*12 = 360
   - m[3][4] = 3*12*5 = 180
   Then:
   - m[1][3] = min( m[1][1]+m[2][3]+5*10*12=0+360+600=960, m[1][2]+m[3][3]+5*3*12=150+0+180=330 ) = 330
   - m[2][4] = min( m[2][2]+m[3][4]+10*3*5=0+180+150=330, m[2][3]+m[4][4]+10*12*5=360+0+600=960 ) = 330
   Finally:
   - m[1][4] = min( m[1][1]+m[2][4]+5*10*5=0+330+250=580, m[1][2]+m[3][4]+5*3*5=150+180+75=405, m[1][3]+m[4][4]+5*12*5=330+0+300=630 ) = 405

3. Final Answer:

   405 -> Option B

4. Quick Check:

   Minimum cost = 405 [OK]

Hint: Trace inner loops carefully to find minimum cost [OK]

Common Mistakes:

• Misindexing arrays starting from 0 instead of 1
• Incorrectly calculating multiplication costs
• Ignoring initialization of m[i][j]

4. Identify the error in the following C code snippet for Matrix Chain Multiplication and select the fix:

int p[] = {2, 3, 4};
int n = 2;
int m[3][3] = {0};
for (int L = 2; L <= n; L++) {
    for (int i = 1; i <= n - L + 1; 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]*p[k]*p[j];
            if (q < m[i][j])
                m[i][j] = q;
        }
    }
}
printf("%d", m[1][n]);

medium

A. Change p[i]*p[k]*p[j] to p[i-1]*p[k]*p[j]

B. Initialize m array with -1 instead of 0

C. Change loop to start i from 0 instead of 1

D. Use float instead of int for m array

Solution

1. Step 1: Identify the indexing error in cost calculation

   The multiplication cost formula uses p[i]*p[k]*p[j], but correct indexing for dimensions array is p[i-1]*p[k]*p[j] because p has length n+1 and matrices are from i to j.

2. Step 2: Fix the formula to use correct indices

   Changing to p[i-1]*p[k]*p[j] fixes the dimension mismatch and ensures correct cost calculation.

3. Final Answer:

   Change p[i]*p[k]*p[j] to p[i-1]*p[k]*p[j] -> Option A

4. Quick Check:

   Dimension indexing = p[i-1]*p[k]*p[j] [OK]

Hint: Remember dimension array indexing starts at i-1 for cost [OK]

Common Mistakes:

• Using wrong indices in multiplication cost formula
• Not initializing m array properly
• Incorrect loop ranges causing out-of-bound errors

5. Given matrices with dimensions p = {40, 20, 30, 10, 30}, what is the minimum number of scalar multiplications needed to multiply the chain? Use the Matrix Chain Multiplication approach.

hard

A. 18000

B. 30000

C. 26000

D. 24000

Solution

1. Step 1: Understand matrix dimensions and problem size

   p = {40, 20, 30, 10, 30} means matrices: 40x20, 20x30, 30x10, 10x30. We need minimum multiplication cost for 4 matrices.

2. Step 2: Calculate minimum multiplication cost using DP

   Calculate costs:
   - m[1][2] = 40*20*30 = 24000
   - m[2][3] = 20*30*10 = 6000
   - m[3][4] = 30*10*30 = 9000
   Calculate m[1][3]:
   - (m[1][1]+m[2][3]+40*20*10) = 0 + 6000 + 8000 = 14000
   - (m[1][2]+m[3][3]+40*30*10) = 24000 + 0 + 12000 = 36000
   Minimum = 14000
   Calculate m[2][4]:
   - (m[2][2]+m[3][4]+20*30*30) = 0 + 9000 + 18000 = 27000
   - (m[2][3]+m[4][4]+20*10*30) = 6000 + 0 + 6000 = 12000
   Minimum = 12000
   Calculate m[1][4]:
   - (m[1][1]+m[2][4]+40*20*30) = 0 + 12000 + 24000 = 36000
   - (m[1][2]+m[3][4]+40*30*30) = 24000 + 9000 + 36000 = 69000
   - (m[1][3]+m[4][4]+40*10*30) = 14000 + 0 + 12000 = 26000
   Minimum = 26000

3. Final Answer:

   26000 -> Option C

4. Quick Check:

   Minimum scalar multiplications = 26000 [OK]

Hint: Calculate costs for all splits, pick minimum [OK]

Common Mistakes:

• Calculating only one split instead of all
• Mixing up matrix dimensions in multiplication
• Forgetting to add multiplication costs properly