sicp-ex-1.14



<< Previous exercise (1.13) | sicp-solutions | Next exercise (1.15) >>


WARNING: one reader found this analysis to be highly inaccurate.

Solution to Exercise 1.14. 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?

The tree illustration can be as given below. The order of value of coins have been reversed inorder to reduce the size of the diagram. As said in the section 1.2.2, order of coins does not matter. So the resultant procedure will be as given below.

  
 (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) 50) 
         ((= kinds-of-coins 2) 25) 
         ((= kinds-of-coins 3) 10) 
         ((= kinds-of-coins 4) 5) 
         ((= kinds-of-coins 5) 1))) 
                                 11 => 50 25 10 5 1
                                       4|0
                             +----------+---------+
                             |                    |
                        11 => 25 10 5 1      -39 => 50 25 10 5 1
                            4|0
                    +--------+-------+
                    |                |
               11 => 10 5 1    -14 => 25 10 5 1
                   3|1
            +-------+--------------------------------------+
            |                                              |
      11 => 5 1                                       1=> 10 5 1
           1|2                                            1|0
    +-------+-------+                                 +----+---------+
    |               |                                 |              |
 11=> 1          6 => 5 1                           1=> 5 1      -9 => 10 5 1
                   1|1                               1|0
           +--------+----+                      +-----+---+
           |             |                      |         |
        6 => 1        1 => 5 1               1 => 1     -4=> 5 1
                        1|0
                    +----+----+
                    |         |
                1 => 1     -4=> 5 1

Rspns777: The analysis below is wrong. For a correct one, see: http://www.ysagade.nl/2015/04/12/sicp-change-growth/

TLDR;
Time Complexity:  O(n^5) 
Space Complexity: O(n)

The exercise also asks for the orders of growth in space and time, as the amount increases. (Forgive any errors or imprecision in my answer, as my analysis skills are still very basic.)

Space required (maximum height of the call tree) grows linearly with the amount, as it is determined by the number of times the smallest denomination divides into the amount. i.e. O(a)

Time required (number of operations) grows in relation to O(a^n). i.e. O(a * a * a * ...) since the 2nd branch is O(a), and the first branch is called O(n) times.

I made a pretty svg version of the call tree for 11 cents, generated by a slightly modified version of the function writing a Graphviz description.

qu1j0t3

I think space is O(n^2) as this is not a tail recursive function.


No, space for this recursive version is O(n). The only space requirement is remembering the stack, and stack depth increases with depth of the tree.

For a true tail-recursive function, there is only ever one function in the stack, so space would be O(1).

samphilipd?


Another more formal approach:

count-change space order of growth:

count-change time order of growth:

  1. cc(n, 1) = O(n)
  2. cc(n, 2) = cc(n, 1) + cc(n-5, 2)
  3. each 2. step is O(n) and there are roughly n/5 such steps
  4. so we have O(n^2)
  5. by analogue we get O(n^k) (k currencies) for cc(n, k)

Feel free to expand if needed.

gollum0


Slightly more detailed analysis is here. The wonderful explanation below has wrong space asymptotics.

voom4000


Another wonderful explanation


For fun, here is an ASCII graph if we keep the denominations in their original order:

(count-change 11)
|
(cc 11 5)__
|          \
(cc 11 4)   (cc -39 5)
|       \___
|           \
(cc 11 3)   (cc -14 4)
|       \_______________________________________________________
|                                                               \
(cc 11 2)                                                      (cc 1 3)
|       \_________________________                              |     \__
|                                 \                             |        \
(cc 11 1)                        (cc 6 2)                      (cc 1 2) (cc -9 3)
|       \___                      |     \__                     |     \__
|           \                     |        \                    |        \
(cc 11 0)   (cc 10 1)            (cc 6 1) (cc 1 2)             (cc 1 1) (cc -4 2)
         __/ |                 __/ |       |     \__            |     \__
        /    |                /    |       |        \           |        \
(cc 10 0)   (cc 9 1)  (cc 6 0)   (cc 5 1) (cc 1 1) (cc -4 2)   (cc 1 0) (cc 0 1)
         __/ |                 __/ |       |     \__
        /    |                /    |       |        \
(cc 9 0)    (cc 8 1)  (cc 5 0)   (cc 4 1) (cc 1 0) (cc 0 1)
         __/ |                 __/ |
        /    |                /    |
(cc 8 0)    (cc 7 1)  (cc 4 0)   (cc 3 1)
         __/ |                 __/ |
        /    |                /    |
(cc 7 0)    (cc 6 1)  (cc 3 0)   (cc 2 1)
         __/ |                 __/ |
        /    |                /    |
(cc 6 0)    (cc 5 1)  (cc 2 0)   (cc 1 1)
         __/ |                 __/ |
        /    |                /    |
(cc 5 0)    (cc 4 1)  (cc 1 0)   (cc 0 1)
         __/ |
        /    |
(cc 4 0)    (cc 3 1)
         __/ |
        /    |
(cc 3 0)    (cc 2 1)
         __/ |
        /    |
(cc 2 0)    (cc 1 1)
         __/ |
        /    |
(cc 1 0)    (cc 0 1)

I believe the algorithm has space complexity O(n) and time complexity O(2^n). The space complexity being O(n) is fairly self-evident once you expand the initial function call (cc 11 5) until the only calls left to expand are of the form (cc n 1). The latter type of call will inevitably expand to an addition of n zeros to 1 (in fact, the way I see it the algorithm would be dramatically more efficient if there were a check for this condition), and no matter what, there will always be a call to (cc <amount> 1) somewhere in the tree, creating a subtree with a call stack <amount> calls deep. The time complexity being O(2^n) is a little less obvious but consider that on each call to cc, there are only three possible outcomes:

1) Both conditions fail and two additional calls to cc are made 2) One condition fails and one is met, resulting in one additional call to cc 3) Both conditions are satisfied and the expression can be evaluated

The third case entails incrementing the amount of ways to change the amount, and the second case indicates that the amount is smaller than the current denomination. Now imagine the worst case scenario:

a) The amount to change would be very large b) The number of different denominations would also be very large c) The value of each denomination would be very low

However, and I may be wrong on this one, even if only a) were true that would stilll mean that practically every call to cc would result in two additional calls, which more or less creates a binary tree kinds-of-coins-levels deep. Each level has twice as many calls to cc as the one before, hence O(2^n).