Divide and Conquer

Pseudo-code

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

        if (change exists in coinArray)
            coin_count[index of change] = 1
            return coin_count, 1
        else if (change = 0)
            return coin_count, 0

        min_coins = infinity

        for (i = 1 to change/2)
            coin_count_left, min_coins_left =
                CHANGE_SLOW(coin_array, i) 
            coin_count_right, min_coins_right =
                CHANGE_SLOW(coin_array, change - i)
            total_coins = min_coins_left + min_coins_right

            if total_coins < min_coins:
                min_coins = total_coins

                for (j in coin_count_left/right)
                    coin_count =
                        coin_count_left[j] + coin_count_right[j]

    return coin_count, min_coins

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 check our $k$ coins to see if any are exactly equal to our change amount. After that, a for-loop runs from 1 to $\frac{n}{2}$, where this value is assumed to be an integer. Our recurrence is of the form:

$$T(n) = \sum_{i = 1}^{\frac{n}{2}} \left( T(n - i) + T(i) \right) + k$$

The loop only needs to run to $\frac{n}{2}$ due to the fact that values above $\frac{n}{2}$ will simply recompute a sum already computed. As an exmpale, consider the case where $n = 5$. When $i=2$, we compute $T(3) + T(2)$. If we continued on to $i=3$, we would compute $T(2) + T(3) \equiv T(3) + T(2)$.

While this recurrence is difficult to solve, we can consider the case without our optimization and consider it an upper bound. Consider the recurrence:

$$T(n) = \sum_{i=1}^{n-1} \left( T(n-i) + T(i) \right) + k$$

The resulting sum will look like:

$$T(n-1) + T(n-2) + \ldots + T(2) + T(1) + T(1) + T(2) + \ldots + T(n-2)+T(n-1)$$

Which we can see is equivalent to:

$$ 2\cdot(T(n-1) + T(n-2) + \ldots + T(2) + T(1))$$

So, our recurrence can be expressed as:

$$ T(n) = 2 \sum_{i = 1}^{n-1} T(i) + k $$

As an additional step, we note that $T(n-1)$ is:

$$T(n-1) = 2\sum_{i = 1}^{n-2} T(i) + k $$

We can compute the difference between $T(n)$ and $T(n-1)$ as:

$$ T(n) - T(n-1) = \left( 2 \sum_{i = 1}^{n-1} T(i) + k\right) - \left(2 \sum_{i = 1}^{n-2} T(i) + k \right)$$$$ T(n) - T(n-1) = 2T(n-1) $$

Solving for T(n), we find that: $$T(n) = 3T(n-1)$$

By the Muster Theorem, with $a = 3$, $b = 1$, and $d = 0$, we can say that $T(n)$ is $O(3^n)$.