Solution for exercise 1.14 from SICP

Solution for exercise 1.14 from SICP

Draw the tree illustrating the process generated by the count-change procedure 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?

(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-coins)
  (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)))

First, call tree:

Red and Green is end leaves of tree, red calculated to 0, green to 1.

Now let’s figure out order of growth. First, easy part, space. Space is O(n + m), where n is amount and m is kind-of-coins. You can see it on call tree, first we decrease m, until it not 1, after that - n.

Now about time growth.

For simplicity let’s imagine that every type of coin have a same nominal. First, lets look at cc 4 1

From the picture we can see that cc(n, 1) grown as 2n+1

Lets see at cc(4 2)

And cc(4 3)

We can see that on each level there is n calls n times of previous level plus n plus 1.

So, we can say that (I’ll use \(T(n,m)\) here instead of cc)

\[T(n, m) = 1 + n + \sum_{i=1}^{n}T(i, m - 1)\] \[T(n, 1) = 2n + 1\]

Reminder

\[\sum_{i=1}^{n}i =\frac{n(n+1)}{n}=n^2 + n\]

Let’s unwrap a couple of recursion levels

\[T(n, 1) = 2n + 1\] \[T(n, 2) = 1 + n + \sum_{i=1}^{n}T(i, 1)= \newline 1 + n+\sum_{i=1}^{n}(2i + 1)\] \[T(n, 3) = 1 + n + \sum_{i=1}^{n}T(i, 2)= \newline 1 + n + \sum_{i=1}^{n}(1 + i+\sum_{i=1}^{n}(2i + 1))\] \[T(n, 4) = 1 + n + \sum_{i=1}^{n}T(i, 3)= \newline 1 + n+\sum_{i=1}^{n}(1 + i + \sum_{i=1}^{n}(1 + i +\sum_{i=1}^{n}(2i + 1)))\]

So we can calculate that:

\[O(T(n, 1)) = n\] \[O(T(n, 2)) = n^2\] \[O(T(n, 3)) = n^3\] \[O(T(n, 4)) = n^4\]

So, again, there is a clear pattern. We can say that \(O(T(n, m)) = n^m\)