Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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)

share|improve this question

migrated from cstheory.stackexchange.com Dec 2 '12 at 18:19

This question came from our site for theoretical computer scientists and researchers in related fields.

1 Answer 1

up vote 0 down vote accepted

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/.

share|improve this answer
    
Links might break. Maybe you can add a summary of the proof or the basic idea behind it to make your answer more valuable. –  A.Schulz Dec 2 '12 at 18:36
    
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... –  NeuronQ Dec 2 '12 at 19:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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