# Time complexity for count-change procedure in SICP

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)

-

## migrated from cstheory.stackexchange.comDec 2 '12 at 18:19

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

## 1 Answer

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

-
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