Greedy Coin Change Time Complexity

Question

I'm trying to figure out the time complexity of a greedy coin changing algorithm. (I understand Dynamic Programming approach is better for this problem but I did that already). I'm not sure how to go about doing the while loop, but I do get the for loop.

I have the following where D[1...m] is how many denominations there are (which always includes a 1), and where n is how much you need to make change for.

This is my algorithm:

CoinChangeGreedy(D[1...m], n)
    numCoins = 0
    for i = m to 1
        while n ≥ D[i]
            n -= D[i]
            numCoins += 1
    return numCoins

Answer 1

Let look at the edge cases.

At the worse case D include only 1 element (when m=1) then you will loop n times in the while loop -> the complexity is O(n).

If m>>n (m is a lot bigger then n, so D has a lot of element whom bigger then n) then you will loop on all m element till you get samller one then n (most work will be on the for-loop part) -> then it O(m).

Button line: O(max(m,n))

Hope that helps!

Answer 2

Thanks for the help. I changed around the algorithm I had to something I could easily calculate the time complexity for. Here's what I changed it to:

CoinChangeGreedy(D[1...m], n)
    numCoins = 0
    for i = m to 1
        if n/D[i] ≥ 1
            numCoins = numCoins + (n/D[i])
            n = n - [(n/D[i]) * D[i]]
    return numCoins

Where I calculated this to have worst-case = best-case \in \Theta(m)