Skip to main content
Computer Science

Return to Answer

deleted 181 characters in body
Source Link
Shi
Shi
  • 35
  • 4

The runtime of $0/1$ knapsack problem using dynamic programming is $O(nW)$. Now assume that $W = 2^n$, then the runtime of the above algorithm is $O(n2^n)$, which is not a polynomial runtime in $n$. The runtime of the algorithm depends upon $n$ and $W$. If your input is represented in the binary then $W$ takes constant space in the input. Now look at the runtime $O(nW)$, and try to figure out the relation between constant and $W$.

The runtime of $0/1$ knapsack problem using dynamic programming is $O(nW)$. Now assume that $W = 2^n$, then the runtime of the above algorithm is $O(n2^n)$, which is not a polynomial runtime in $n$. The runtime of the algorithm depends upon $n$ and $W$. If your input is represented in the binary then $W$ takes constant space in the input. Now look at the runtime $O(nW)$, and try to figure out the relation between constant and $W$.

The runtime of $0/1$ knapsack problem using dynamic programming is $O(nW)$. Now assume that $W = 2^n$, then the runtime of the above algorithm is $O(n2^n)$, which is not a polynomial runtime in $n$. The runtime of the algorithm depends upon $n$ and $W$.

Source Link
Shi
Shi
  • 35
  • 4

The runtime of $0/1$ knapsack problem using dynamic programming is $O(nW)$. Now assume that $W = 2^n$, then the runtime of the above algorithm is $O(n2^n)$, which is not a polynomial runtime in $n$. The runtime of the algorithm depends upon $n$ and $W$. If your input is represented in the binary then $W$ takes constant space in the input. Now look at the runtime $O(nW)$, and try to figure out the relation between constant and $W$.