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?
(define (denom coin-number)
(cond ((= coin-number 5) 50)
((= coin-number 4) 25)
((= coin-number 3) 10)
((= coin-number 2) 5)
((= coin-number 1) 1)))
(define (cc amount coin-number)
(cond ((or (< amount 0)
(< coin-number 0)) 0)
((= amount 0) 1)
((= coin-number 0) 0)
(else
(+ (cc (- amount (denom coin-number)) coin-number)
(cc amount (- coin-number 1))))))
(define (count-change n)
(cc n 5))
The orders of growth of the space is \( \Theta(n) \) where n is the number of coins. The number
of steps used by this process as the amount to be changed increases at \( \Theta(n^c) \).
I have no idea if this is true nor do I have a proof. This is merely a guess. I need a little more
algorithm analysis under my belt to solve this one.