I am learning anaysis of algorithms and design techniques in algorithms. While studying knapsack problem it is mentioned that though knapsack is O(nW) where n is number of items and W is weight. It is non polynomial as explained below.
The size of input is log(W) bits for the weight (and O(n) for "value" and "weight" arrays).
So, the input size of weight is j = log(W) (and not mere W). So, W = 2ʲ (as binary is used).
The final complexity is O(n * W)
This O(n * W) can be rewritten as O(n * 2^j), which exponential in the size of the input.
With above argument, all algorithms for example sorting algorithm is O(nlogn) which also becomes exponential as "n" is expressed as 2^j.
I am getting confused.
Determining whether or not an algorithm runs in "polynomial time" requires a stricter definition of "input size" than is required for describing the running time of an algorithm. For example, the following algorithm runs in O(n) time, but not in polynomial time:
count_down(n)
i = n
while i > 0 do
i--
The loop iterates n times and does O(1) work* per iteration, where n is the input number, so its time complexity is O(n). In most situations there is no problem with saying that this algorithm takes O(n) time.
However, for the purposes of whether or not an algorithm runs in polynomial time, what we mean is whether its running time is bounded by a polynomial function of the input size, usually measured in bits. The number of bits required to represent the number n is about log₂ n, so that's the input size, and O(n) is not bounded by a polynomial in log₂ n.
This doesn't apply for sorting algorithms, since for those n means the length of an array rather than the magnitude of a number. It is not possible to represent an array of length n using only O(log n) bits; it takes O(n) bits. So the running time O(n log n) or O(n²) is bounded by a polynomial function of the input size in this case, because the input size is n instead of log₂ n. This implies that such sorting algorithms do run in polynomial time.
*Caveat: decrementing an integer takes O(1) amortized time if the integer is modified in place. In a language like Python where integers are immutable objects, this takes O(log n) time because of the need to copy that many bits to a new object.