SICP Exercise 1.14: Counting Change

Draw the tree illustrating the process generated by the count-change procedure of section 1.2.2 in making change for 11 cents. What are the orders of growth of the space and number of steps used by this process as the amount to be changed increases?

Drawing the tree is a pretty straightforward, but not overly exciting. I used Graphviz to give me something legible. Well, it's legible if you click on it and zoom in to view it full size:

Note that I've not drawn in the arrow showing the progress through the tree as they do in the book for showing the processing of (fib 5), but it follows the same breadth-first, left-to-right progression. I have, however, put in the results returned by the individual leaf nodes (i.e. 0 if the leaf node does not generate a valid combination of coins, 1 otherwise).

We can easily see that the deepest path through the tree is to follow the left-most path until you reach (cc 11 1) and then follow the right-most path from then on. This path first works through decrementing kinds-of-coins until it reaches the last denomination, which also happens to be the smallest: 1¢. It then works through decrementing amount by this denomination until it reaches 0.

If we take n as the amount and m as the kinds-of-coins then this gives us the order of growth of the space of the process: Θ(n+m)

Looking at the tree it seems like the order of growth of the number of steps is much more complex to determine.  So to simplify it let's start by looking at the order of growth of the number of steps when we have fewer available denominations, discarding the largest denominations first.  And to simplify talking about it, remember from above that we're using n as the amount and m as the kinds-of-coins.

The simplest case is when m = 0.  I.e. when there are no denominations to give change with.  In this case the first call to cc terminates without any recursive calls, and with a fixed number of steps.  So when m = 0 the order of growth of the number of steps is Θ(1).

When m = 1 and n ≥ 1, the first call to cc makes two recursive calls to cc: one with m' = 1 and n' = n -1 and the other with m' = 0 and n' = n.  The former of these calls repeats this process until a call is made with n = 0 and, as we only have one denomination to deal with, the smallest (1¢), there will be n + 1calls to cc with m' = 1 including the initial call, and each one of these other than the last one will also make a call with m' = 0.  That makes a total of 2n + 1 calls to cc, each of which has a fixed number of steps, so when m = 1 the order of growth of the number of steps is Θ(2n + 1) = Θ(n).

When m = 2 and n ≥ 1, again the first call to cc makes two recursive calls to cc: this time one has m' = 2 and n' = n -1 and the other with m' = 1 and n' = n. And again the former of these calls repeats this process until a call is made with n = 0.  Gosh, it's almost like there's a pattern we should spot here.  This time, however, we're using the 5¢ denomination so there will be n/5 + 1 calls to cc with m' = 2 including the initial call.  Similar to before each one of these other than the last one will also make a call with m' = 1.  The n/5 + 1 calls to cc with m' = 2 will have the values for n' of {n, n - 5, n - 10, ..., n - 5⌊(n/5)⌋}, the last value of which will be in the range -5 < (n - 5⌊(n/5)⌋) ≤ 0.  Now each one of these calls other than the last one also makes an additional 2n' + 1 calls to cc (as it makes a call to cc with m' = 1, and we already figured this out above), giving a total of 2n' + 2 calls to cc for each of the values of n' > 0, plus one more call to cc for the final call.

To make things easy on ourselves we can assume that 5 is a factor of n and then rewrite the values for n' as {5(n/5), 5(n/5 - 1), 5(n/5 - 2), ..., 5, 0}.  If we ignore 0, as that only requires a single call to cc, reverse this sequence and take out the factor of 5 we can restate this as the sequence {1, 2, ..., (n/5) - 1, (n/5)}, with values requiring 10n' + 10 calls to cc.  In other words, we need to calculate the sum between 1 and n/5 of 10n' + 10, and then add 1, or:

      n/5
  1 + ∑ (10i + 10)
      i=1
        n/5
= 1 + 10∑ (i + 1)
        i=1

Now we know that the sum of integers between 1 and x can be expressed as x(x + 1)/2, so the sum of i + 1 between 1 and x is going to be (x + 1)(x + 2)/2 - 1.  Substituting this into the equation gives:

  1 + 10((n/5) + 1)((n/5) + 2)/2 - 1
= 10((n/5) + 1)((n/5) + 2)/2
= 5((n/5) + 1)((n/5) + 2)
= (n + 5)((n/5 + 2)
= n2/5 + 5n/5 + 2n + 10
= n2/5 + 3n + 10

So when m = 2, we require a total of n²/5 + 3n + 10 to cc, each of which has a fixed number of steps, giving the order of growth of the number of steps as Θ(n²/5 + 3n + 10) = Θ(n²).

Hopefully you'll forgive me at this point when I make the assertion that the same pattern repeats for the larger numbers of denominations: when m = 3 there are n/10 calls with m = 2, which means n/10 calls to an  Θ(n²) procedure, giving an Θ(n³) order of growth, and so on.  In general the order of growth in the number of steps is Θ(n^m), and so when we have m = 5, we can state that the order of growth in the number of steps is Θ(n⁵).