Solution to Exercise 1.14:
Click to enlarge.
The count-change is Θ(n) in space. Like the fib procedure, the space required is equal to the maximum depth of the tree, which occurs on the combination that is all pennies.
I believe, though I could very well be wrong, that the process is Θ(n2) in time as the calls to cc tend to double with increments to n.
I couldn’t get conclusive timing numbers out of DrScheme to confirm this belief. Here’s the code I was using to test
(require (lib "19.ss" "srfi"))
(map (lambda (amount)
(let ((start-time (current-time time-process))
(change (count-change amount))
(end-time (current-time time-process)))
(let ((diff (time-difference end-time start-time)))
(list (time-second diff) (time-nanosecond diff)))))
(list 100 200 300 400))
The output was ((0 160000) (0 2810000) (0 1560000) (1 6560000)). I don’t understand why the third time was consistently less than the second. Anybody care to enlighten me?
Posted by Ken Dyck in Programming
