0 1 Knapsack Problem in DSA Typescript - Time & Space Complexity

Time Complexity: 0 1 Knapsack Problem

O(n * W)

Understanding Time Complexity

We want to understand how the time needed to solve the 0 1 Knapsack problem grows as the number of items and the knapsack capacity increase.

How does the number of steps change when we add more items or increase the capacity?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function knapsack(weights: number[], values: number[], capacity: number): number {
  const n = weights.length;
  const dp: number[][] = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let w = 1; w <= capacity; w++) {
      if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
      } else {
        dp[i][w] = dp[i - 1][w];
      }
    }
  }
  return dp[n][capacity];
}
    

This code solves the 0 1 Knapsack problem using dynamic programming by filling a table of size (number of items + 1) by (capacity + 1).

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops over items and capacity filling the dp table.
• How many times: Outer loop runs n times (number of items), inner loop runs capacity times.

How Execution Grows With Input

As we add more items or increase capacity, the number of steps grows by multiplying these two factors.

Input Size (n items, capacity W)	Approx. Operations
10 items, capacity 50	About 10 * 50 = 500 steps
100 items, capacity 1000	About 100 * 1000 = 100,000 steps
1000 items, capacity 10,000	About 1000 * 10,000 = 10,000,000 steps

Pattern observation: The steps grow roughly by multiplying the number of items by the capacity, so doubling either doubles the work.

Final Time Complexity

Time Complexity: O(n * W)

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

Common Mistake

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

[OK] Correct: The inner loop runs for every capacity value up to W, so capacity directly affects the total steps.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming improves over brute force and why capacity matters in performance.

Self-Check

"What if we used a recursive solution without memoization? How would the time complexity change?"