<< 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.

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:

- O(n) because max depth is n

count-change time order of growth:

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

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)