SICP Exercise 1.14: orders of growth of count-change

"Life is all about sharing. If we are good at something, pass it on." - Mary Berry

SICP Exercise 1.14: orders of growth of count-change

2021-09-28

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 count-change procedure:

 1(trace-define (count-change amount)
 2    (cc amount 5))
 3
 4(trace-define (cc amount kinds-of-coins)
 5    (cond ((= amount 0) 1)
 6        ((or (< amount 0) (= kinds-of-coins 0)) 0)
 7        (else (+ (cc amount
 8                     (- kinds-of-coins 1))
 9                 (cc (- amount
10                        (first-denomination kinds-of-coins))
11                     kinds-of-coins)))))
12
13(define (first-denomination kinds-of-coins)
14    (cond ((= kinds-of-coins 1) 1)
15          ((= kinds-of-coins 2) 5)
16          ((= kinds-of-coins 3) 10)
17          ((= kinds-of-coins 4) 25)
18          ((= kinds-of-coins 5) 50)))

In making changes for 11 cents, this procedure can be illustrated by a tree:

 1                                                      (11, 5)
 2                                                  _______|_______
 3                                                 |               |
 4                                             (11, 4)        (-39, 5)
 5                                         _______|_______         |
 6                                        |               |        |
 7                                    (11, 3)         (-14, 4)     0
 8                          ____________|____________     |
 9                         |                         |    |   
10                      (11, 2)                    (1, 3) 0
11                  ______|______                _____|_____
12                 |             |              |           |
13              (11, 1)       (6, 2)         (1, 2)      (-9, 3)
14              __|__          __|__         __|__           |
15             |     |        |     |       |     |          |
16         (11, 0) (10, 1) (6, 1) (1, 2) (1, 1) (-4, 2)      0
17            |      |       |     __|__   |__     |
18            |      |       |    |     |     |    |
19            0    (9, 1)    1 (1, 1) (-4, 2) 1    0
20                   |           |      |
21                   |           |      |
22                   1           1      0

Verify by running the above procedure in debug mode:

  1$ racket 1.14-count-change.rkt 11
  2>(count-change 11)
  3>(cc 11 5)
  4> (cc 11 4)
  5> >(cc 11 3)
  6> > (cc 11 2)
  7> > >(cc 11 1)
  8> > > (cc 11 0)
  9< < < 0
 10> > > (cc 10 1)
 11> > > >(cc 10 0)
 12< < < <0
 13> > > >(cc 9 1)
 14> > > > (cc 9 0)
 15< < < < 0
 16> > > > (cc 8 1)
 17> > > > >(cc 8 0)
 18< < < < <0
 19> > > > >(cc 7 1)
 20> > > > > (cc 7 0)
 21< < < < < 0
 22> > > > > (cc 6 1)
 23> > > >[10] (cc 6 0)
 24< < < <[10] 0
 25> > > >[10] (cc 5 1)
 26> > > >[11] (cc 5 0)
 27< < < <[11] 0
 28> > > >[11] (cc 4 1)
 29> > > >[12] (cc 4 0)
 30< < < <[12] 0
 31> > > >[12] (cc 3 1)
 32> > > >[13] (cc 3 0)
 33< < < <[13] 0
 34> > > >[13] (cc 2 1)
 35> > > >[14] (cc 2 0)
 36< < < <[14] 0
 37> > > >[14] (cc 1 1)
 38> > > >[15] (cc 1 0)
 39< < < <[15] 0
 40> > > >[15] (cc 0 1)
 41< < < <[15] 1
 42< < < <[14] 1
 43< < < <[13] 1
 44< < < <[12] 1
 45< < < <[11] 1
 46< < < <[10] 1
 47< < < < < 1
 48< < < < <1
 49< < < < 1
 50< < < <1
 51< < < 1
 52< < <1
 53> > >(cc 6 2)
 54> > > (cc 6 1)
 55> > > >(cc 6 0)
 56< < < <0
 57> > > >(cc 5 1)
 58> > > > (cc 5 0)
 59< < < < 0
 60> > > > (cc 4 1)
 61> > > > >(cc 4 0)
 62< < < < <0
 63> > > > >(cc 3 1)
 64> > > > > (cc 3 0)
 65< < < < < 0
 66> > > > > (cc 2 1)
 67> > > >[10] (cc 2 0)
 68< < < <[10] 0
 69> > > >[10] (cc 1 1)
 70> > > >[11] (cc 1 0)
 71< < < <[11] 0
 72> > > >[11] (cc 0 1)
 73< < < <[11] 1
 74< < < <[10] 1
 75< < < < < 1
 76< < < < <1
 77< < < < 1
 78< < < <1
 79< < < 1
 80> > > (cc 1 2)
 81> > > >(cc 1 1)
 82> > > > (cc 1 0)
 83< < < < 0
 84> > > > (cc 0 1)
 85< < < < 1
 86< < < <1
 87> > > >(cc -4 2)
 88< < < <0
 89< < < 1
 90< < <2
 91< < 3
 92> > (cc 1 3)
 93> > >(cc 1 2)
 94> > > (cc 1 1)
 95> > > >(cc 1 0)
 96< < < <0
 97> > > >(cc 0 1)
 98< < < <1
 99< < < 1
100> > > (cc -4 2)
101< < < 0
102< < <1
103> > >(cc -9 3)
104< < <0
105< < 1
106< <4
107> >(cc -14 4)
108< <0
109< 4
110> (cc -39 5)
111< 0
112<4
1134

Orders of growth

From section 1.2.2:

In general, the number of steps required by a tree-recursive process will be proportional to the number of nodes in the tree, while the space required will be proportional to the maximum depth of the tree.

Space

The maximum depth of the tree will always be the branch that represents the case of all pennies (cc n 1):

 1> > >(cc 11 1)
 2> > > (cc 11 0)
 3< < < 0
 4> > > (cc 10 1)
 5> > > >(cc 10 0)
 6< < < <0
 7> > > >(cc 9 1)
 8> > > > (cc 9 0)
 9< < < < 0
10> > > > (cc 8 1)
11> > > > >(cc 8 0)
12< < < < <0
13> > > > >(cc 7 1)
14> > > > > (cc 7 0)
15< < < < < 0
16> > > > > (cc 6 1)
17> > > >[10] (cc 6 0)
18< < < <[10] 0
19> > > >[10] (cc 5 1)
20> > > >[11] (cc 5 0)
21< < < <[11] 0
22> > > >[11] (cc 4 1)
23> > > >[12] (cc 4 0)
24< < < <[12] 0
25> > > >[12] (cc 3 1)
26> > > >[13] (cc 3 0)
27< < < <[13] 0
28> > > >[13] (cc 2 1)
29> > > >[14] (cc 2 0)
30< < < <[14] 0
31> > > >[14] (cc 1 1)
32> > > >[15] (cc 1 0)
33< < < <[15] 0
34> > > >[15] (cc 0 1)
35< < < <[15] 1
36< < < <[14] 1
37< < < <[13] 1
38< < < <[12] 1
39< < < <[11] 1
40< < < <[10] 1
41< < < < < 1
42< < < < <1
43< < < < 1
44< < < <1
45< < < 1
46< < <1

So, the orders of growth of the space will be O(n).

Number of steps

I cannot solve this part. So I googled for the solution and this one helped me understand how to calculate time complexity of this procedure. I will note it down for the future reference.

Look at the code:

1    (cond ((= amount 0) 1)
2        ((or (< amount 0) (= kinds-of-coins 0)) 0)
3        (else (+ (cc amount
4                     (- kinds-of-coins 1))
5                 (cc (- amount
6                        (first-denomination kinds-of-coins))
7                     kinds-of-coins)))))

(cond ((= amount 0) 1) performs only one operation O(1). If using only pennies, then:

 1T(n, 1) = 1 + T(n, 0) + T(n-1, 1)
 2T(n, 1) = 1 + 1 + T(n-1, 1)
 3
 4T(n - (n-1), 1) = 1 + 1 + T(0, 1) = 1 + 1 + 1 = 3
 5T(n - (n-2), 1) = 1 + 1 + T(n - (n-1), 1) = 1 + 1 + 3 = 5
 6T(n - (n-3), 1) = 1 + 1 + T(n - (n-2), 1) = 1 + 1 + 5 = 7
 7T(n - (n-4), 1) = 1 + 1 + T(n - (n-3), 1) = 1 + 1 + 7 = 9
 8...
 9
10T(n, 1) = 2n + 1

Verify this by running (cc 11 1) in debug mode and counting the number of calls of cc:

 1$ racket 1.14-count-change.rkt 11
 2>(count-change 11)
 3>(cc 11 1)
 4> (cc 11 0)
 5< 0
 6> (cc 10 1)
 7> >(cc 10 0)
 8< <0
 9> >(cc 9 1)
10> > (cc 9 0)
11< < 0
12> > (cc 8 1)
13> > >(cc 8 0)
14< < <0
15> > >(cc 7 1)
16> > > (cc 7 0)
17< < < 0
18> > > (cc 6 1)
19> > > >(cc 6 0)
20< < < <0
21> > > >(cc 5 1)
22> > > > (cc 5 0)
23< < < < 0
24> > > > (cc 4 1)
25> > > > >(cc 4 0)
26< < < < <0
27> > > > >(cc 3 1)
28> > > > > (cc 3 0)
29< < < < < 0
30> > > > > (cc 2 1)
31> > > >[10] (cc 2 0)
32< < < <[10] 0
33> > > >[10] (cc 1 1)
34> > > >[11] (cc 1 0)
35< < < <[11] 0
36> > > >[11] (cc 0 1)
37< < < <[11] 1
38< < < <[10] 1
39< < < < < 1
40< < < < <1
41< < < < 1
42< < < <1
43< < < 1
44< < <1
45< < 1
46< <1
47< 1
48<1
491
50
51$ for amount in (seq 1 11); echo -n "T($amount, 1): "; racket 1.14-count-change.rkt $amount | grep -c 'cc'; end
52T(1, 1): 3
53T(2, 1): 5
54T(3, 1): 7
55T(4, 1): 9
56T(5, 1): 11
57T(6, 1): 13
58T(7, 1): 15
59T(8, 1): 17
60T(9, 1): 19
61T(10, 1): 21
62T(11, 1): 23

Let’s go one step further with 2 kind of coins:

1T(n, 2) = 1 + T(n, 1) + T(n-5, 2)
2T(n, 1) = 2n + 1
3T(n-5, 2) = 1 + T(n-5, 1) + T(n-10, 2) = 1 + (2n + 1) + T(n-10, 2)
4T(n-10, 2) = 1 + (2n + 1) + (2n + 1) + T(n-15, 2)
5...
6
7T(n, 2) = (n/5) * 2n + 1

When k = 3:

1T(n, 3) = 1 + T(n, 2) + T(n-10, 3)
2T(n, 2) = (n/5) * 2n + 1
3T(n-10, 3) = 1 + T(n-10, 2) + T(n-20, 3) = 1 + ((n/5) * 2n + 1) + T(n-20, 3)
4...
5
6T(n, 3) = (n/10) * ((n/5) * 2n + 1)

k = 4:

1T(n, 4) = (n/25) * T(n, 3)

k = 5:

1T(n, 5) = (n/50) * T(n, 4)

So, the time complexity of the count-change procedure with 5 kinds of coins is: O(n⁵).

Tags: sicp scheme

Edit on GitHub