0
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 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
    Commented Oct 20, 2015 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
    Commented Oct 20, 2015 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
    Commented Oct 20, 2015 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
    Commented Oct 20, 2015 at 11:57
  • $\begingroup$ @DavidRicherby Exactly the opposite interpretation is intended. $\endgroup$
    – Yuval Filmus
    Commented Oct 20, 2015 at 18:02

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\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
    Commented Oct 20, 2015 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
    Commented Oct 20, 2015 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
    Commented Oct 20, 2015 at 17:47
  • $\begingroup$ You should be able to work it out yourself. $\endgroup$
    – Yuval Filmus
    Commented Oct 20, 2015 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
    Commented Oct 20, 2015 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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