4
$\begingroup$

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)

$\endgroup$
3
$\begingroup$

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)$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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://wqzhang.wordpress.com/2009/06/09/sicp-exercise-1-14/.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Links might break. Maybe you can add a summary of the proof or the basic idea behind it to make your answer more valuable. $\endgroup$ – A.Schulz Dec 2 '12 at 18:36
  • $\begingroup$ 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... $\endgroup$ – NeuronQ Dec 2 '12 at 19:39
  • 1
    $\begingroup$ @A.Schulz link broke :-( $\endgroup$ – Philip Kirkbride Jul 19 '17 at 19:48
  • $\begingroup$ @A.Schulz thank God we have waybackmachine: wayback.archive.org/web/20141122124458/http://… :) ...btw, I don't have time for this, but if you do and write a proper answer to this question I will accept it instantly! $\endgroup$ – NeuronQ Jul 20 '17 at 7:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.