<< Previous exercise (1.13) | sicp-solutions | Next exercise (1.15) >>
A mathematically rigorous and very clear solution is given by Sébastien Gignoux at his SICP Solutions website. The process is linear in space. It is O(a^n) in time, where a = amount and n = number of denominations of coins. Any comments below to the contrary are inaccurate. BrianHagerty
WARNING: one reader found this analysis to be highly inaccurate. For a correct one, see: (dead link: www.ysagade.nl/2015/04/12/sicp-change-growth/)
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 in order 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
Per Rspns777: The analysis below is wrong.
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 (dead link: telegraphics.com.au/~toby/sicp/ex1-14.svg pretty svg version) of the call tree for 11 cents, generated by a slightly modified version of the function writing a Graphviz description.
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:
Feel free to expand if needed.
Slightly more detailed analysis is here. The wonderful explanation below has wrong space asymptotics.
voom4000
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)
QUESTION
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?
ANSWER
Tree of the process for changing an amount a using n kinds of coins:
a,n / \ a,n−1 a−d(n),n /\ / \ … … a−d(n),n−1 a−2×d(n),n /\ / \ … … a−2×d(n),n−1 … /\ / \ … … a−k×d(n),n−1 a−(k+1)×d(n),nwhere a − k × d(n) > 0 and a − (k + 1) × d(n) ≤ 0, that is k = ⌈a/d(n)⌉ − 1.
The space required by the process is the height of the tree and grows as Θ(a) with a and n:
The number of steps required by the process is the number of internal vertices of the tree and grows as Θ(a^n) with a and n:
R(a, 0) = 1, R(a, n) = 1 + ⌈a/d(n)⌉ + Σ_{i = 0}^{⌈a/d(n)⌉ − 1} R(a − i × d(n), n − 1) = Θ(a^n).