## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 1.14

## Problem

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?

## Solution

Here's a version of `count-change` which counts the number of times it
is called. This count is useful for validating our answer to the
exercise.

(define count 0) (define (count-change amount) (set! count 0) (cc amount 5)) (define (cc amount kinds-of-coins) (let () (set! count (+ 1 count)) (cond ((= amount 0) 1) ((or (< amount 0) (= kinds-of-coins 0)) 0) (else (+ (cc amount (- kinds-of-coins 1)) (cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins)))))) (define (first-denomination kinds-of-coins) (cond ((= kinds-of-coins 1) 1) ((= kinds-of-coins 2) 5) ((= kinds-of-coins 3) 10) ((= kinds-of-coins 4) 25) ((= kinds-of-coins 5) 50)))

The count for `(count-change 11)` is 55. The graph for this evaluation isn't shown here, but if you draw it on paper, you can
see that it generates a tree recursive process.

Each time procedure `cc` is called, it returns 1, 0 or the sum of two
subtrees. Let's say, then, that each invocation of `cc`, that is,
each node in the evaluation tree, performs one operation.

For `amount` *n* and `kinds-of-coins` 5, the number of operations
performed by procedure `cc` is 1 plus the number of operations
performed by the subtree generated by `(cc n 4)`, plus the number of
operations performed by the subtree generated by `(cc (- n 50) 5)`.
Let's use *N(n,m)* to denote the number of operations performed by a
subtree `(cc n m)`. Then we have:

*N*(*n*,5) = 1 + *N*(*n*,4) + *N*(*n* − 50,5)

Let's expand the first *N* term by repeating this process for `(cc n 4)`:

*N*(*n*,4) = 1 + *N*(*n*,3) + *N*(*n* − 25,4)

Keep expanding the first *N* term of each subtree:

*N*(*n*,3) = 1 + *N*(*n*,2) + *N*(*n* − 10,3)

*N*(*n*,2) = 1 + *N*(*n*,1) + *N*(*n* − 5,2)

*N*(*n*,1) = 1 + *N*(*n*,0) + *N*(*n* − 1,1)

`(cc n 0)` is a termination case: it performs only a single operation
(returns 0):

*N*(*n*,0) = 1

*N*(*n*,1) = 1 + 1 + *N*(*n* − 1,1)

Let's now consider the other subtree of `(cc n 1)`, `(cc (- n 1) 1)`:

*N*(*n* − 1,1) = 1 + *N*(*n* − 1,0) + *N*(*n* − 2,1)

Once again, `(cc (- n 1) 0)` is a termination case and performs only a
single operation. This process continues until the `amount` argument
of `cc` is `(- n n)`, at which point we've fully evaluated the `(cc n 1)`
subtree:

*N*(*n* − *n*,1) = 1

Working our way back up:

*N*(*n* − (*n* − 1),1) = 1 + 1 + 1 = 3

*N*(*n* − (*n* − 2),1) = 1 + 1 + *N*(*n* − (*n* − 1),1) = 1 + 1 + 3 = 5

*N*(*n* − (*n* − 3),1) = 1 + 1 + *N*(*n* − (*n* − 2),1) = 1 + 1 + 5 = 7

*N*(*n* − (*n* − 4),1) = 1 + 1 + *N*(*n* − (*n* − 3),1) = 1 + 1 + 7 = 9

It's easy to see that this process continues until we're back to
`(cc n 1)`:

*N*(*n*,1) = 1 + 1 + *N*(*n* − 1,1) = 2*n* + 1

We can verify this by drawing the graph for `(cc 11 1)` and counting
the number of nodes. Note that the amount of storage required for
an applicative-order evaluation of the `(cc n 1)` subtree is also
proportional to 2*n* + 1, since the `+` operations are deferred until
the value of each subtree is calculated.

When we're dealing with θ-notation orders of growth, we can
ignore constant factors, so it's sufficient to say that evaluating
`(cc n 1)` requires order *n* number of steps and order *n* storage, since
2*n* + 1 is linear in *n*. Dropping these constant terms makes it
easier to calculate orders of growth for the other terms in the
process tree.

`(count-change n)` generates a tree-recursive process. We know from
the text that tree-recursive processes require space proportional to
the depth of the tree, and we know that `(cc n 1)` generates the
deepest subtree of the process (since other subtrees reduce the size
of *n*), so we can say at this point that `count-change` requires space
of order *n* (i.e., linear).

We also know from the text that tree-recursive processes require a
number of operations proportional to the number of nodes in the
tree, so we have to count the remaining number of operations before
we can answer the second part of the question, i.e., `count-change`'s order of growth of
operations.

Let's go back to the root of the subtree which generated `(cc n 1)`:

*N*(*n*,2) = 1 + *N*(*n*,1) + *N*(*n* − 5,2)

We know the value of the first N term. The 2nd N term is:

*N*(*n* − 5,2) = 1 + *N*(*n* − 5,1) + *N*(*n* − 10,2)

This expansion continues until *n* is <= 0, or roughly *n*/5 times, since
each expansion of the 2nd term subtracts 5 from its `amount` argument.
Each one of these expansions produces an *N(a 1)* term, where *a* is the amount, and
each of those terms produces 2*a* + 1 operations. Subtracting a
constant from *n* at each step doesn't change the fact that each step
is a linear (order *n*) process, so we can ignore the subtraction when
calculating the order of growth. *n* times *n*/5 steps is *n*^{2} / 5 steps.
This term overwhelms the 2*n* + 1 steps we calculated for the previous
branch, so we can ignore the 2*n* + 1 term now and say that
calculating `(cc n 2)` has order *n*^{2} / 5 steps.

Now we consider the next node up the tree, the one which generated
`(cc n 2)`:

*N*(*n*,3) = 1 + *N*(*n*,2) + *N*(*n* − 10,3)

The analysis for this step is similar to the one we performed for *N(n,2)*: calculating `(cc (- n 10) 3)` produces roughly *n*/10 more
nodes, each of which evaluates `(cc x 2)`. We know that evaluating
`(cc x 2)` is order *x*^{2} / 5, so `(cc n 3)` is roughly *n*/10 times that,
*n*^{3} / 50. Again, the *n*^{3} term dominates the growth of the process,
so we can ignore the lesser orders of growth of the other nodes
we've considered and say that `(cc n 3)` has order *n*^{3} / 50 growth.

Calculating *N(n,4)* and *N(n,5)* follows similar logic. It's
then straightforward to show that the number of steps required to evaluate `(cc n 5)` is θ(*n*^{5}).