What is the time complexity of this coin change algorithm?

Question

I solved the coin changing problem on leetcode https://leetcode.com/problems/coin-change-2/.

This is the code I wrote:

    def change(self, amount: int, coins: List[int]) -> int:
        def helper(amount, coins, ind):
            if amount == 0:
                return 1
            if amount < 0:
                return 0
            if (amount, ind) in dp:
                return dp[(amount, ind)]

            res = 0
            for i in range(ind, len(coins)):
                res  += helper(amount - coins[i], coins, i)

            dp[(amount, ind)] = res
            return res

        coins.sort()
        dp = {}
        return helper(amount, coins, 0)

And I notice I struggle a lot with analyzing the time complexities of algorithms with memoization. For example in this case I think we have amount * number of coins sub-problems --> hence the algorithm runs in O(amount * number of coins * number of coins) the second number of coins in my factor comes from the fact that for each sub-problem we have to go through the loop for i in range(ind, len(coins)): to add up the results.

However it seems that this solution is actually O(amount * number of coins) from what I read (and the bottom up approach is O(amount * number of coins)). What is the right answer ?

I seem to struggle a lot with loops inside recursive functions, it sometimes seem like we count them in the time complexity, and other times they are already "priced in" in the sub-problems like I suspect is the case here.

You're analysis seems correct to me. You have O(amount * number of coins) cells in your table and to compute any cell in the table you run a loop (number of coins) times. The code you wrote has this complexity. It's likely that there is a different algorithm that has O(amount * number of coins) complexity. — Enrico Borba
– Enrico Borba, Commented Nov 18, 2019 at 23:47

d_darric · Accepted Answer · 2019-11-19 09:16:56Z

2

As Enrico Borba commented:

Your analysis seems correct to me. You have O(amount * number of coins) cells in your table and to compute any cell in the table you run a loop (number of coins) times. The code you wrote has this complexity. It's likely that there is a different algorithm that has O(amount * number of coins) complexity.

– Enrico Borba

answered Nov 19, 2019 at 9:16

d_darric

3972 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

What is the time complexity of this coin change algorithm?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related