An algorithm A for solving the knapsack problem has time com

An algorithm A for solving the knapsack problem has time complexity (nC), where C is the capacity of the knapsack and n is the number of items. Is A a polynomial time algorithm?

Solution

O(nC) looks like a polynomial time,but is not polynomial.It is pseudo-poynomial.Time complexity can be measured as length of bits of input.Here input is C.

Now consider C=1,000,000,000,000.This can be represented only in 40 bits.Hence,input sie can be considered as only 40,but when we try to compute this it will go to exponential.Computational runtime will use factor of C which is 2⁴⁰.Hence,runing time complexity can be considered as O(n2^bits(C)) which is exponential in time.