# 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

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