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!