Rod Cutting Problem in DSA C - Time & Space Complexity

Time Complexity: Rod Cutting Problem

O(2^n)

Understanding Time Complexity

We want to understand how the time needed to solve the rod cutting problem changes as the rod length grows.

How does the number of steps grow when the rod gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int rodCutting(int price[], int n) {
    if (n == 0) return 0;
    int max_val = -1;
    for (int i = 1; i <= n; i++) {
        int val = price[i - 1] + rodCutting(price, n - i);
        if (val > max_val) max_val = val;
    }
    return max_val;
}
    

This code tries all ways to cut the rod and picks the best price sum.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop tries all cut lengths from 1 to n.
• How many times: For each call with length n, it calls itself recursively for smaller lengths, repeating this many times.

How Execution Grows With Input

Each rod length n calls itself for all smaller lengths, creating many repeated calls.

Input Size (n)	Approx. Operations
10	Thousands of calls
20	More than a million calls
30	Billions of calls

Pattern observation: The number of calls grows very fast, much faster than just doubling.

Final Time Complexity

Time Complexity: O(2^n)

This means the time needed doubles roughly with each increase in rod length, making it very slow for large rods.

Common Mistake

[X] Wrong: "The code runs in linear time because it just loops from 1 to n."

[OK] Correct: Each loop iteration calls the function again, causing many repeated calls that multiply quickly.

Interview Connect

Understanding this helps you explain why naive recursion can be slow and why dynamic programming is better.

Self-Check

"What if we store results of smaller rods to avoid repeated calls? How would the time complexity change?"

Practice

1. What is the main goal of the Rod Cutting Problem in algorithms?

easy

A. To minimize the number of cuts made on the rod

B. To maximize the total profit by cutting the rod into pieces

C. To find the shortest rod length possible

D. To count the total number of ways to cut the rod

Solution

1. Step 1: Understand the problem objective

   The rod cutting problem aims to cut a rod into pieces to get the highest total price from selling those pieces.

2. Step 2: Identify the goal

   The goal is to maximize profit, not minimize cuts or count ways.

3. Final Answer:

   To maximize the total profit by cutting the rod into pieces -> Option B

4. Quick Check:

   Maximize profit = maximize total price [OK]

Hint: Focus on maximizing profit, not minimizing cuts or counting ways [OK]

Common Mistakes:

• Thinking the goal is to minimize cuts
• Confusing the problem with counting combinations
• Assuming the rod length changes

2. Which of the following is the correct way to declare the price array for a rod of length 4 in C?

easy

A. int price[4] = {2, 5, 7, 8};

B. int price[] = {2, 5, 7, 8};

C. int price[5] = {0, 2, 5, 7, 8};

D. int price[4] = (2, 5, 7, 8);

Solution

1. Step 1: Understand array indexing for rod prices

   Prices are usually stored with index representing length, so for length 1 to 4, index 0 is unused or zero.

2. Step 2: Check array declaration correctness

   int price[5] = {0, 2, 5, 7, 8}; declares array of size 5 with price[0]=0, then prices for lengths 1 to 4, which is correct.

3. Final Answer:

   int price[5] = {0, 2, 5, 7, 8}; -> Option C

4. Quick Check:

   Index 0 unused, prices start at 1 [OK]

Hint: Use size n+1 with zero at index 0 for convenience [OK]

Common Mistakes:

• Using parentheses instead of braces for array initialization
• Declaring array size smaller than needed
• Not including zero price at index 0

3. What will be the output of the following C code snippet for rod length 4?

int price[5] = {0, 2, 5, 7, 8};
int n = 4;
int dp[5] = {0};
for (int i = 1; i <= n; i++) {
  int max_val = 0;
  for (int j = 1; j <= i; j++) {
    int val = price[j] + dp[i - j];
    if (val > max_val) max_val = val;
  }
  dp[i] = max_val;
}
printf("%d", dp[n]);

medium

A. 10

B. 9

C. 8

D. 7

Solution

1. Step 1: Trace dp array computation for each length

   Calculate dp[1] to dp[4]: dp[1] = max(price[1]+dp[0]) = 2 dp[2] = max(price[1]+dp[1], price[2]+dp[0]) = max(2+2,5+0)=5 dp[3] = max(price[1]+dp[2], price[2]+dp[1], price[3]+dp[0]) = max(2+5,5+2,7+0)=7 dp[4] = max(price[1]+dp[3], price[2]+dp[2], price[3]+dp[1], price[4]+dp[0]) = max(2+7,5+5,7+2,8+0)=10

2. Step 2: Identify final dp[n] value

   dp[4] = 10 is printed.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Max profit for length 4 = 10 [OK]

Hint: Calculate dp bottom-up, check all cuts for max profit [OK]

Common Mistakes:

• Forgetting to consider all cut lengths j
• Using wrong indices for price or dp
• Not initializing dp array properly

4. Identify the error in the following C code snippet for rod cutting:

int price[5] = {0, 2, 5, 7, 8};
int n = 4;
int dp[5] = {0};
for (int i = 1; i <= n; i++) {
  int max_val = 0;
  for (int j = 1; j < i; j++) {
    int val = price[j] + dp[i - j];
    if (val > max_val) max_val = val;
  }
  dp[i] = max_val;
}
printf("%d", dp[n]);

medium

A. max_val should be initialized to -1

B. dp array size is too small

C. price array initialization is incorrect

D. Inner loop should run till j <= i, not j < i

Solution

1. Step 1: Analyze inner loop range

   The inner loop runs from j=1 to j

2. Step 2: Correct the loop condition

   Changing inner loop to j <= i ensures all possible cuts including full length are considered.

3. Final Answer:

   Inner loop should run till j <= i, not j < i -> Option D

4. Quick Check:

   Include full length cut by using j <= i [OK]

Hint: Inner loop must include full length cut (j <= i) [OK]

Common Mistakes:

• Using j < i misses full rod cut
• Incorrect dp array size causes errors
• Initializing max_val to 0 is correct here

5. Given a rod of length 5 and prices price = {0, 2, 5, 7, 8, 10}, what is the maximum profit and the cuts to achieve it?
Use the rod cutting logic to find the best cuts and profit.

hard

A. Profit = 12, Cuts = [2, 3]

B. Profit = 11, Cuts = [1, 4]

C. Profit = 10, Cuts = [5]

D. Profit = 13, Cuts = [1, 1, 3]

Solution

1. Step 1: Calculate maximum profit using dp

   Calculate dp for lengths 1 to 5: dp[1]=2 dp[2]=max(2+2,5)=5 dp[3]=max(2+5,5+2,7)=7 dp[4]=max(2+7,5+5,7+2,8)=10 dp[5]=max(2+10,5+7,7+5,8+2,10)=12

2. Step 2: Determine cuts for maximum profit

   Profit 12 achieved by cutting rod into lengths 2 and 3 (price[2]+price[3]=5+7=12).

3. Final Answer:

   Profit = 12, Cuts = [2, 3] -> Option A

4. Quick Check:

   Max profit 12 with cuts 2 and 3 [OK]

Hint: Check all cut pairs for max sum profit [OK]

Common Mistakes:

• Choosing no cuts or single cut only
• Not checking all combinations for max profit
• Confusing profit values with cut lengths