Expert: John OConnor - 4/9/2010

Question
QUESTION: Hi there,
When I read about the coin change problem, I usually get the information that the computational complexity of the dynamic programing algorithm used for this problem is of the order Theta(nxk), where n is the desired amount (of cents, for example), and k is the number of different coin denominations.
My question is this: Why (or when) is this algorithm considered exponential in time. The reason I ask this is because I found in some articles that this algorithm is NOT necessary polynomial even if its complexity is the above-mentioned Theta(nxk).

Thanks.

ANSWER: Hey Samir,

For an algorithm to be of exponential time complexity, it has to Big O(n^k).  Theta puts an upper bounds on the time complexity, which is at nxk, meaning this algorithm will most likely never be exponential (it's always geometric, with respect to n and k).

Hope this helps.

---------- FOLLOW-UP ----------

QUESTION: Hi again,
I hate to bother you again but I need to clarify my question.
I understand your reasoning with regard to the big O notation. But the articles in question don't dispute that. Rather, the argument there is that although the computational complexity is polynomial: O(nxk), the input n is not; it's exponential in size of the bits (digits), so these problems are called pseudo-polynomial. So, how can I know when to look for number of digits as the input or just the numerical value? Can you give me a definite answer if the coin change problem is polynomial or exponential?

Answer
Thanks for the clarification!

This problem is unfortunately outside of my expertise.  However, I will do my best to provide some resources and general discussion about this problem in the hopes that it may help.

It seems that the Coin Change problem, as a variant of the Knapsack problem, is NP-Hard, with the variant you describe (unbounded) being NP-Complete.  If you're referring to the unbounded version of this algorithm, this this is a very difficult question to answer.

The academic answer would be that this algorithm itself is polynomial, and that the amortized time is exponential.  I cannot find anything suggesting that there is an algorithm for determining the largest "N" before the dynamic programming version becomes exponential.

This may not be that helpful, but a solution that yields acceptable results in most situations is George Dantzig's greedy approximation algorithm (also called the "grocers algorithm"): http://en.wikipedia.org/wiki/Knapsack_problem#Greedy_approximation_algorithm.  You can divide the input (N) by the largest denomination of coins until it is no longer divisible.  Then, move to the next denomination down.  This will yield an unoptimized result for the unbounded problem, but may be quite suboptimal for the bounded version of this problem.

My apologies that my answer could not be more helpful.  Thanks for your patience.