Exercise 1.14. (second part)

What are the orders of growth of the space and number of steps used by this 
process as the amount to be changed increases?

Each call to (cc a n), for a > 0, n > 0, creates two more calls to cc.
One of these calls decrements n, the other reduces a.

Let Amt_a be an amount $0.11 which has already been calculated.

Amt_b = $0.12.

Then calculation of (cc 12 5) includes the calculation of (cc 12 4) and (cc (12 - 50) 5)
(cc 12 3) (cc (12 - 25) 4)
(cc 12 2) (cc 2 3)




A top-level call to (count-change a) results in calls to

(cc a 5)

(cc a 4)

(cc a 3)

(cc a 2)

(cc a 1)

(cc a 0)

as well as:

(cc (a-50) 5)

(cc (a-25) 4)

(cc (a-10) 3)

(cc (a-5) 2)

(cc (a-1) 1)




If we then add 50 cents to a call...

(cc a 5)

= (cc (a-50) 5) + (cc a 4)

In other words, calculating (cc a 5) is equivalent to calculating (cc (- a 50) 5) and (cc a 4).

The difference between (cc (- a 50) 5) and (cc a 5) is (cc a 4), so the shape of (cc a 4) can tell us about the order of growth as amount increases.

So, how many steps are required to calculate (cc a 4)?

In (cc a 1) we will have a chain of a calls to (cc a 1), (cc a-1 1), ..., (cc 0 1) (2n+1 calls including the (cc _ 0) calls)

So the steps in (cc a 4) is at least n.

There is also (cc a 2), which includes (cc a 1), already considered, and adds (cc (- a 5) 2)

(For large a, the subtracted 5 may be ignored.)

Thus we have (cc (- a 5) 1) again, which is O(n), and (cc (- a 10) 2)...
So we have a/5 calls to (cc x 2), where average x is a/2, each of which calls (cc x 1), for an average number of steps a, so we have a*(a/5) steps, which is O(n^2).

Looking at (cc a 3), we have a call to (cc a 2), already considered, and a call to (cc (- a 10) 3)

We see that we will have a total of a/10 calls to (cc _ 3), plus (a/10) calls to (cc x 2) with an average x again of a/2.

So we have a sum as i → a of a/10 O(i^2) calls, this is O(n^3).

Similarly the (cc a 4) call will be O(n^4), and then the number of steps of the count-change function is O(n^5) in the amount.

As for the space consumed, in evaluating a call to (cc a n) the most deeply-nested stack of calls will be the chain from (cc a n) to (cc a 1) to (cc 0 1), which will include a + 5 nested calls, so stack size is O(n).