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
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.