Greedy

Pseudo-code

GREEDY(coin_array, change)
    coin_count = [0,...,coin_array.length - 1] = 0 

    i = coin_count.length - 1

    while change > 0
        if change >= coin_array[i]
            change -= coin_array[i]
            coin_count[i]++
        else
            i--

    return coin_count, sum(coin_count[0,...,coin_count.length])

Runtime Analysis

The algorithm takes two inputs: coinArray and change. The parameter coinArray contains all of the possible denominations of coins that can be used to make change with. The parameter change is the amount of change that needs to be composed of various combinations of coins that are denoted in the coinArray. From this point forward we will refer to the length of the coinArray as $k$ and the value for change as $n$.

As can be seen from the pseudo-code above we first start with a while-loop that starts with $n=change$ and continues until $n=0$ (until change has been made). Within that loop each element of coinArray (from largest to smallest, $k-1$ to $0$ is checked against the remaining value of change $n$ to be made and subtracted if possible. If a given coin is too large to be subtracted from the remaining change, then the next lower coin is attempted. Because the lowest coin value is guaranteed by the problem statement to have $value=1$, a solution is to the problem is guaranteed.

The while-loop is the only iterating construct. But how long does it run? In the very best case - the highest coin value in coinArray wil be equal to change $n$. An example might be [1 25 50 100] with $n=100$. In this case, the loop will run just once for $O(1)$ complexity. In the worst case - all coin values in coinArray (other than 1) are greater than change $n$. An example might be [1 25 50 100] with $n=24$.

In this worst case the while-loop will run $k$ times - once for each value stored in coinArray as it searches for a coin value less than or equal to $n$. In this case the only coin value that works is $1$ and therefore the while loop will run $n$ times - subtracting off a value of $1$ for each execution of the loop. This leaves us with a runtime of:

The $-1$ above is removing double booking of the first subtraction of $value=1$ from $n$ (both at the end of the k "loop" and beginning of the n "loop"). The constant term $-1$ drops off as well as the $O(1)$ term because the $O(k + n)$ will dominate as $n$ or $k$ become increasingly large. Therefore the finalized runtime of the greedy change making algorithm is: