I have an algorithm here that counts the number of ways that n cents can be represented using the following denominations:
quarter: 25 cents
dime: 10 cents
nickel: 5 cents
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.