Time Complexity for Knapsack Dynamic Programming solution

Question

I saw the recursive dynamic programming solution to 0-1 Knapsack problem here. I memoized the solution and came up with the following code.

private static int knapsack(int i, int W, Map<Pair<Integer, Integer>>, Integer> cache)
{
 if (i < 0) {
    return 0;
 }
Pair<Integer, Integer> pair = new Pair<>(i,W);
if (cache.contains(pair)) {
  return cache.get(pair)
}
int result = -1;
if (weights[i] > W) {
    result = knapsack(i-1, W);
} else {
    result = Math.max(knapsack(i-1, W), knapsack(i-1, W - weights[i]) + values[i]);
}
cache.put(pair, result);
return result;
}

Can someone explain to me why should the time complexity be O(nW) where n is the number of items and W is the restriction on weight.

Answer 1

It's more obvious if you think through what the table would look like in a tabular implementation of the DP. It has items on one axis and max achievable weight on the other, with one row per possible integer weight. For some weight sets, the table must be densely filled to find the optimum answer. These same weight sets will require Omega(nW) pairs in your memo hash, ergo since each entry is a constant time computation, the same time to compute all. It's a good exercise to think through how to get the costly weight sets, so I'll let that to you.