14

Exercise 1.14: Draw the tree illustrating the process generated by the count-change procedure of 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?”

                     count-change 11
                           |
                           |
                        cc 11 3
                           /\
                          /  \
                         /    \
                        /      \
                    cc 11 2   cc 1 3
                      /\         |
                     /  \        1
                    /    \
                   /      \
               cc 11 1   cc 6 3
                   |         /\
                   1        /  \
                           /    \
                          /      \
                      cc 6 1    cc 1 2
                         |         |
                         1         1

$$ResourceOfSpace(n) = \theta(2^{\frac{n}{50}})$$

$$ResourceOfTime(n) = \theta(2^{\frac{n}{50}+1})$$