Unbounded Knapsack Problem in DSA C - Time & Space Complexity

Time Complexity: Unbounded Knapsack Problem

O(n * W)

Understanding Time Complexity

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

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.

int unboundedKnapsack(int W, int n, int val[], int wt[]) {
    int dp[W+1];
    for (int i = 0; i <= W; i++) dp[i] = 0;
    for (int i = 0; i <= W; i++) {
        for (int j = 0; j < n; j++) {
            if (wt[j] <= i) {
                dp[i] = dp[i] > dp[i - wt[j]] + val[j] ? dp[i] : dp[i - wt[j]] + val[j];
            }
        }
    }
    return dp[W];
}
    

This code finds the maximum value for a knapsack of capacity W using unlimited copies of n items.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops: outer loop runs from 0 to W, inner loop runs over n items.
• How many times: Outer loop runs W+1 times, inner loop runs n times for each outer iteration.

How Execution Grows With Input

As the knapsack capacity W grows, the outer loop runs more times. For each capacity, we check all n items.

Input Size (W)	Approx. Operations (n * W)
10	10 * n
100	100 * n
1000	1000 * n

Pattern observation: The work grows linearly with both the knapsack capacity and the number of items.

Final Time Complexity

Time Complexity: O(n * W)

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

Common Mistake

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

[OK] Correct: The capacity W controls how many times the outer loop runs, so it directly affects the 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?"