CODEWITHSUNDEEP
pythonalgorithmbig-o
user50449
user50449

Reputation: 91

Complexity of this algorithm in big O notation?

def ways(n, coin):
    if n < 0 or len(coin) == 0:
        return 0
    if n > 0:
        return ways(n, coin[:-1]) + ways(n-coin[-1], coin)
    return 1

Called like so:

ways(100, [1, 5, 10, 25, 50]) with an output of 292

The algorithm calculates the number of ways that one can make change for 100 using only 50, 25, 10, 5, 1. The original problem uses $1 and 50 cents, 25 cents, etc...but I've simplified this by multiplying by 100.

My problem is as follows. What is the big-o complexity?

The algorithm seems to branch out by a factor of 2, but its not quite O(2^N) as can be seen by having a depth of greater than 292 with an input of N=5.

I note the number of ways it can branch out depends. For instance, one possible way can be from n=100, to n=50, to n=0. Two branches, another way is n=50, n=25, n=0, etc etc. And I know that the maximum depth possible for one of the branches is N.

So it must be O(2^M) but what is M in relation to N?

NOTE: Sorry if this caused confusion, but n = the current value of money, and i'm assuming (capital) N is the length of the coin array

Upvotes: 2

Views: 508

Answers (2)

Gerard Rozsavolgyi
Gerard Rozsavolgyi

Reputation: 5074

Ollie gave the right answer for the complexity in n with coins constant as shows this time graphic computed with your function and drawn with matplotlib (with some smoothing) : Time computing ways() with coins constant

We recognize a nice Parabola (n^2)

If we take n as a constant and make number of coins vary, (coins randomly generated), the curve is much steeper, and as you thought exponential

Time computing ways() with n fixed

There are better algorithms as memoized version :

# memways(n, k, coins) = number of ways of making 
# change of n with less or equal k coins
calculated = {}
def memways(n, k, coins):
    if n<0:
        return 0
    if (n, k) in calculated:
        return calculated[n,k]
    if k == 0:
        v = 1
    else:
        v = memways(n-coins[k], k, coins) + memways(n, k-1, coins)
    calculated[n,k] = v
    return v

Upvotes: 1

OJFord
OJFord

Reputation: 11140

O(n^2).

It's a recursive function over n, modifying only coins in the recursive call, giving n^2.

The addition of the second recursive call is inconsequential, since it is over some x < n.

Upvotes: 1

Related Questions