[Solved]: Time complexity for count-change procedure in SICP

Problem Detail: 

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)

Asked By : NeuronQ

Answered By : NeuronQ

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7105