title: Time Complexity for Knapsack Dynamic Programming solution
body: <p>I saw the recursive dynamic programming solution to 0-1 Knapsack problem <a href="https://stackoverflow.com/questions/7774769/how-do-i-solve-the-classic-knapsack-algorithm-recursively">here</a>. I memoized the solution and came up with the following code.</p>
  
  <pre><code>private static int knapsack(int i, int W, Map&lt;Pair&lt;Integer, Integer&gt;&gt;, Integer&gt; cache)
  {
   if (i &lt; 0) {
      return 0;
   }
  Pair&lt;Integer, Integer&gt; pair = new Pair&lt;&gt;(i,W);
  if (cache.contains(pair)) {
    return cache.get(pair)
  }
  int result = -1;
  if (weights[i] &gt; 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;
  }
  </code></pre>
  
  <p>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. </p>