# Counting the number of ways to break an amount into coins

I have an algorithm here that counts the number of ways that n cents can be represented using the following denominations:

1. quarter: 25 cents

2. dime: 10 cents

3. nickel: 5 cents

4. pennies: 1 cent

There are an unlimited number of each available. Here is my algorithm

def Coins(amt, cache):
'''
A method to convert denominations in the arr to represent n cents
'''
# pdb.set_trace()

arr = [25, 10, 5, 1] #quarter, dime, nickel, penny
result = 0

if amt < 0:
return 0 #base case

if cache[amt] != 0:
return cache[amt]
if amt == 0:
return 1 #base case

for i in arr:
result += Coins(amt - i, cache)

cache[amt] = result

return result


I want to know what the run time of this algorithm is. I initially thought it would be $O(4^n)$ since each call makes up to 4 recursive calls.

But, for an amt of 10, that would be 1,048,576 and that seems insane. How do I go about finding out what the big $O$ of this is? (I'd appreciate the method to approach the answer rather than the answer directly)

Also, if there is a more efficient version of this algorithm, or any way to improve this algorithm, I'm interested in hearing about it.

• There's no magical tool that will calculate Big O for you. Some would also say Big O is not accurate. Why don't you just measure the actual time it takes for the task to complete to your requirements, and improve it if not satisfactory? – Phrancis Jul 27 '17 at 12:34
• Please take a look at the help center. The first premise of posting a question here is wanting to have your code reviewed. Do you want a review, or do you want a magic tool telling you what the big O notation of your code is? You should take a look at Software Recommendations if it's the latter, but I doubt there are any such accurate tools available. – Mast Jul 27 '17 at 12:40
• @Mast, Phrancis — The OP is clearly asking for help with carrying out an asymptotic (big-O) analysis (not for a magic tool). Analysis of algorithms is an important skill and I think it's reasonable to ask for help with it. I'm not sure if Code Review is the best place, but if not, where is? At cs.stackexchange.com they have a policy of closing "easy" analysis questions like this one. – Gareth Rees Jul 27 '17 at 13:47
• @GarethRees I agree. However, 'What is O(…) and how do I calculate it?' has been asked and answered on Software Engineering. I'm not looking forward to multiple questions a day asking not for a review but just for what their big O score is. – Mast Jul 27 '17 at 14:04
• @Mast This question is now under discussion on Meta. – 200_success Jul 27 '17 at 21:24

## 1 Answer

The way to approach this is to think about how many times Coins is called for each amount $m\le n$.

I claim that Coins is called at most 4 times with any given amount $m$. That's because a call to Coins with the amount $m$ must either be the original call, or else a recursive call from Coins with amount $m+1$, $m+5$, $m+10$ or $m+25$. But recursive calls only happen when the cache is missed, and that can happen only once for each amount (because thereafter the cache has an entry for that amount).

Now you can apply the usual line-by-line analysis (see here for an example) to get a big-O expression for the overall runtime.

• Just out of curiosity, lets assume the cache was not implemented. Would my initial approach of saying this algorithm is O(4^n) be correct? – Zaid Humayun Aug 1 '17 at 6:50
• Your original analysis was fine, since big-O is an upper bound. It just wasn't a tight upper bound. – Gareth Rees Aug 1 '17 at 15:45