Time complexity for count-change procedure in SICP
Order of growth of number of steps: $\theta (n^5)$

We can prove that, in general, the order of growth of number of steps is $\theta (n^m)$, where $m$ is the number of types of coin available. Here is my (very) crude reasoning using induction:


When there is only one type of coin, the number of steps is obviously proportional to n.
Suppose it would take (cc n m) steps to change an amount of $n$ with $m$ types of coin. Now let's consider (cc n m+1): ($A$ is the denomination of the $m$th kind of coin.)



  (cc $n$ $m+1$)
  = (cc $n$ $m$) + (cc $n-A$ $m+1$)
  = (cc $n$ $m$) + (cc $n-A$ $m$) + (cc $n-2A$ $m+1$)
  = (cc $n$ $m$) + (cc $n-A$ $m$) + (cc $n-2A$ $m$) + (cc $n-3A$ $m+1$)
  = ......


It would eventually computes to 

(cc n m) + (cc n-A m) + ... + (cc &lt;something-negative&gt; m+1)


There are approximately $n/A$ items. So the total number of steps would be proportional to $n/A*n^m$, which is proportional to $n^{m+1}$. Thus, the order of growth for number of steps of (cc n m) is $\theta (n^m)$.

Let $m$ be 5, and the order of growth of number of steps is $\theta (n^5)$.