1.14 Exercise 1.14

(Tree not included.)

To figure out the order of growth of the number of steps used in this process (from now on called the time complexity), it’s easiest to start with the case where kinds-of-coins is 1 and then work up to the starting value of 5.

(cc n 1) evaluates like this:

(cc n 1)

(+ (cc n 0) (cc (- n (first-denomination 1)) 1))

(+ (cc n 0) (cc (- n 1) 1))

Since (cc n 0) simply returns 1, it has time complexity O(1). And since every call of cc calls cc one more time until eventually reaching an O(1) base case, (c n 1) has time complexity O(n).

Now suppose we want to evaluate (cc n 2):

(cc n 2)

(+ (cc n 1) (cc (- n 5) 2))

Since 5 is subtracted each time from n, there are n / 5 calls to cc with a kinds-of-coins value of 2. And each of these calls cc with a kinds-of-coints value of 1. Therefore, calls to (cc n 2) have time copmlexity (n / 5) * O(n) = O(n^2).

The process continues similarly: (cc n 3) has time complexity (n / 10) * O(n^2) = O(n^3), (cc n 4) has time complexity (n / 25) * O(n^3) = O(n^4), and (cc n 5), our standard call to cc, has time complexity (n / 50) * O(n^4) = O(n^5).

The important choices in finding the time complexity of the whole process were to start with a base case with a simple time complexity and to notice that incrementing kinds-of-coins gave a process with a time complexity that could be expressed in terms of the last one.

TODO: Space complexity