0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.