Unbounded Knapsack Problem in DSA Typescript - Time & Space Complexity

Time Complexity: Unbounded Knapsack Problem

O(n * m)

Understanding Time Complexity

We want to understand how the time needed to solve the Unbounded Knapsack problem grows as the input size increases.

Specifically, how the number of items and the knapsack capacity affect the work done.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function unboundedKnapsack(capacity: number, weights: number[], values: number[]): number {
  const dp = new Array(capacity + 1).fill(0);
  for (let c = 1; c <= capacity; c++) {
    for (let i = 0; i < weights.length; i++) {
      if (weights[i] <= c) {
        dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);
      }
    }
  }
  return dp[capacity];
}
    

This code finds the maximum value achievable with unlimited copies of given items within the capacity.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops - outer loop over capacity, inner loop over items.
• How many times: Outer loop runs capacity times, inner loop runs number of items times for each capacity.

How Execution Grows With Input

As capacity or number of items grows, the total operations increase by multiplying these two factors.

Input Size (capacity n, items m)	Approx. Operations
n=10, m=5	About 50 operations
n=100, m=5	About 500 operations
n=1000, m=5	About 5000 operations

Pattern observation: Operations grow roughly by multiplying capacity and number of items.

Final Time Complexity

Time Complexity: O(n * m)

This means the time needed grows proportionally with both the knapsack capacity and the number of items.

Common Mistake

[X] Wrong: "The time depends only on the number of items, not the capacity."

[OK] Correct: The outer loop runs for each capacity value, so capacity directly affects total work.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming solves problems efficiently by breaking them into smaller parts.

Self-Check

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