# Fizz Buzz and pseudo-polynomial time

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?

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