Question regarding coin change algorithm (DP and greedy)

Question

The question goes something like this:

Suppose you are living in a country where coins have values that are powers of p, V = [1, 3, 9, 27]. How do you think the dynamic programming and greedy approaches would compare?

Intuitively I want to answer that DP will be faster because greedy runs the same number of comparisons regardless of the relationship between the elements in V. But DP is a recursive call on previous elements, so the fact that there is always a ratio of p between each denomination of V would suggest that DP will end up making less recursive calls. Can anyone confirm my answer or tell me why I'm wrong?

• D.W.: Cross-posted: math.stackexchange.com/q/1978116/14578, cs.stackexchange.com/q/64900/755. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted.

Answer 1

In terms of running time, the greedy algorithm is still going to be faster than the DP algorithm. DP will always produce the optimal solution regardless of values in V. Greedy, on the other hand, takes advantage of extra structure present in some value choices that allow it to effectively ignore possible ways of getting to the goal value. A coin system where the values are powers of p would allow the greedy algorithm to also consistently produce the optimal solution.