Why is the knapsack problem pseudo-polynomial?

by

The running time is O(NW) for an unbounded knapsack problem with N items and knapsack of size W. W is not polynomial in the length of the input though, which is what makes it pseudo-polynomial.

Consider W = 1,000,000,000,000. It only takes 40 bits to represent this number, so input size = 40, but the computational runtime uses the factor 1,000,000,000,000 which is O(240).

So the runtime is more accurately said to be O(N.2bits in W), which is exponential.

Also see:

More Related Contents:

  1. Shortest distance between a point and a line segment
  2. What’s your most controversial programming opinion?
  3. What is a callback function?
  4. Strangest language feature
  5. Is a GUID unique 100% of the time?
  6. Runtime vs. Compile time
  7. What’s your favorite “programmer” cartoon?
  8. De Morgan’s rules explained
  9. What is boxing and unboxing and what are the trade offs?
  10. Code Golf: Number to Words
  11. Is it OK to use DYLD_LIBRARY_PATH on Mac OS X? And, what’s the dynamic library search algorithm with it?
  12. What is name mangling, and how does it work?
  13. Given an integer, how do I find the next largest power of two using bit-twiddling?
  14. How can I find the difference between two angles?
  15. What is an integer overflow error?
  16. What are the advantages of memory-mapped files?
  17. Why does division by zero in IEEE754 standard results in Infinite value?
  18. Is Method Overloading considered polymorphism? [closed]
  19. What is an invariant?
  20. Arguments or parameters? [duplicate]
  21. What is an ideal variable naming convention for loop variables? [closed]
  22. Should we compare floating point numbers for equality against a *relative* error?
  23. Is Sleep() evil?
  24. Recursion or iteration?
  25. What does ‘foo’ really mean? [closed]
  26. Build an ASCII chart of the most commonly used words in a given text [closed]
  27. What are “magic numbers” in computer programming?
  28. Find all complete sub-graphs within a graph
  29. Why are leading zeroes used to represent octal numbers?
  30. What is differential execution?

Leave a Comment