4
$\begingroup$

I am currently taking a course on algorithms, and when reading about the 0/1 Knapsack Problem on Wikipedia I came across a technique which uses dynamic programming and supposedly runs in $O(nW)$ time, which makes sense to me after studying the algorithm. But to my understanding, the 0/1 Knapsack Problem is NP-complete, which means it cannot be solved in polynomial time (that would solve the infamous $N=NP$ problem). The explanation that I have seen for why $O(nW)$ does not run in polynomial time, is that when we're discussing time complexities that depend on numeric values, we're actually not concerned with the value of $W$ but rather the size of its representation. If $W$ is represented in binary, then adding bits would increase the size of $W$ linearly, but the value of $W$ would increase exponentially.

And assuming that I have understood everything correctly thus far, here is my question:

The Fizz Buzz problem can be solved in $O(n)$ time, and is described as a problem that can be solved in linear time according to (for instance) these articles which show up with a Google search: Medium, Jared Nielsen, San Tuon.

But $n$ in Fizz Buzz is simply a numeric value, just like $W$ in the Knapsack Problem. So how come Fizz Buzz is regarded as a problem which can be solved in polynomial time, but the Knapsack Problem is not?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

The running time of the algorithm is linear in terms of $n$, but yes, you're right the algorithm does have a pseudo-polynomial time complexity since the standard is for the running time to be in terms of the number of bits of the input.

The articles don't make this distinction since this they're written for beginners, for whom it'll be hard to grasp the concept of pseudo-polynomial time and the reasoning behind it if they're just getting familiarised with the notion of time complexity.

Improve this answer
$\endgroup$
0
$\begingroup$

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$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I am not exactly sure what the conclusion of tour argument is supposed to be. Also, "If your input is represented in the binary then W takes constant space in the input" what do you mean by this? $\endgroup$
    – Highheath
    Commented Mar 19 at 19:18
  • $\begingroup$ Hi I have edited my answer. $\endgroup$
    – Shi
    Commented Mar 20 at 12:44

Not the answer you're looking for? Browse other questions tagged or ask your own question.