I have the following algorithm in ML:

fun change(till,0,chg,chgs) = chg::chgs
|   change([],amt,chg,chgs) = chgs
|   change(c::till,amt,chg,chgs) = if amt<0 then chgs else change(c::till, amt-c,c::chg, change(till,amt,chg,chgs));

The algorithm takes a list of currency denominations as till and returns all the combinations of denominations which produce the amount amt specified.

And I am trying to show that the number of ways for making change for some value n regardless of order with two change values is O(n). And then trying to figure out what it is for more change values.

It's clear that for one change value it is O(1) as there is only one possible way to make change but I'm not sure how to progress from there.

Any help would be much appreciated.

  • 1
    $\begingroup$ You should check out our reference questions. Also, please add some idea about the algorithm; raw source code is offtopic here. $\endgroup$ – Raphael Oct 20 '15 at 11:46
  • 1
    $\begingroup$ What do you mean by "regardless of order"? If it means that giving you coins 1,1,2,2 is different from 1,2,1,2, then there are exponentially many ways, and I can't think of any other reasonable meaning of "regardless of order". $\endgroup$ – David Richerby Oct 20 '15 at 11:52
  • $\begingroup$ @DavidRicherby That is the terminology used when the question was posed to me, given it was an aside I have not paid much attention to it as part of the general problem. $\endgroup$ – Joshua Oct 20 '15 at 11:57
  • $\begingroup$ @Raphael Thanks, I am taking a look and have updated the question with a description of the algorithm. I can remove the source if wanted also. $\endgroup$ – Joshua Oct 20 '15 at 11:57
  • $\begingroup$ @DavidRicherby Exactly the opposite interpretation is intended. $\endgroup$ – Yuval Filmus Oct 20 '15 at 18:02

Suppose that the two denominations are $a$ and $b$. Every solution to the coin-changing problem is a solution to the equation $\alpha a + \beta b = n$ in non-negative integers $\alpha,\beta$. For every possible value of $\alpha$ there is at most one solution. Since $0 \leq \alpha \leq n/a$, we conclude that there are at most $n/a + 1 = O(n)$ solutions.

  • $\begingroup$ Thank you. Just wondering where the $+ 1$ came from in the conclusion? And also how would this apply to when there are more denominations? $\endgroup$ – Joshua Oct 20 '15 at 13:20
  • 1
    $\begingroup$ If $n/a$ is an integer then there are exactly $1+n/a$ integers in the range $[0,n/a]$. When there are $c$ denominations, the same argument gives an upper bound of $O(n^{c-1})$. $\endgroup$ – Yuval Filmus Oct 20 '15 at 13:22
  • $\begingroup$ Would it be possible if you could give an example of how to use this method for additional denominations (e.g. 3)? That would be very very much appreciated if so. $\endgroup$ – Joshua Oct 20 '15 at 17:47
  • $\begingroup$ You should be able to work it out yourself. $\endgroup$ – Yuval Filmus Oct 20 '15 at 17:48
  • $\begingroup$ So far I've got that $\alpha a + \beta b + \gamma c = n$ and for every $\alpha$ there are at most $n/b + 1$ values. The issue is the next step — a hint would be appreciated. $\endgroup$ – Joshua Oct 20 '15 at 17:55

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.