Time complexity for count-change procedure in SICP

Question

In famous Structure and Interretation of Computer Programs, there is an exercise (1.14), that asks for the time complexity of the following algorithm - in Scheme - for counting change (the problem statement suggests drawing the tree for (cc 11 5) - which looks like this):

 ; count change
 (define (count-change amount)
 (define (cc amount kinds-of-coins)
 (cond ((= amount 0) 1)
 ((or (< amount 0) (= kinds-of-coins 0)) 0)
 (else (+ (cc (- amount
 (first-denomination kinds-of-coins))
 kinds-of-coins)
 (cc amount
 (- kinds-of-coins 1))))))
 (define (first-denomination kinds-of-coins)
 (cond ((= kinds-of-coins 1) 1)
 ((= kinds-of-coins 2) 5)
 ((= kinds-of-coins 3) 10)
 ((= kinds-of-coins 4) 25)
 ((= kinds-of-coins 5) 50)))
 (cc amount 5))

Now... there are sites with solutions to the SICP problems, but I couldn't find any easy to understand proof for the time complexity of the algorithm - there is a mention somewhere that it's polynomial O(n^5)

Answer 1

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:

1. When there is only one type of coin, the number of steps is obviously proportional to n.

2. 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 <something-negative> 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)$.

Answer 2

Probably this was not the right place for this question, but anyway, I found the answer in the meantime, in the form of a mostly "digestible" proof at http://wayback.archive.org/web/20141122124458/http://wqzhang.wordpress.com/2009/06/09/sicp-exercise-1-14/.

• A.Schulz: Links might break. Maybe you can add a summary of the proof or the basic idea behind it to make your answer more valuable.
• NeuronQ: when I find the energy to go from my pen & paper notes to latex I'll write a better explained and formatted version of the proof, as it's pretty ugly, but not this evening :) ...idea is simple, just hard to switch your brain to using induction rigorously to figure out O(n) after years of doing these kind of things guess-wise or not at all, and to be careful on the few calculations...