SICP section 1.2.3
June 28th, 2007 at 5:50 amIn this section the authors provide the standard introduction to orders of growth (big-Oh notation) and give a few simple examples of formulas and their growth orders.
Exercise 1.14
The tree is pretty big, so I’ll refrain from drawing it. However, it is quite clear how it goes. Obviously, the deepest path in the tree happens when the result is the sum in all pennies. So the space is O(n) for n that is the amount we want to change.
Figuring out the time complexity here is much more challenging, because the recursion formula is hard to solve analytically. Initially I thought it’s exponential, but Thomas Morgan convinced me that it is polynomial, somewhere in the order of O(N^5). If you have a proof, please let me know.
Note that similarly to the recursive Fibonacci, there is a lot of repetitiveness – we’ll be solving the same problem over an over again in different sub-branches of the tree. Memoization can improve matters here a lot.
Exercise 1.15
Here is the code rewritten in CL, along with some printing to find out how many times p is called:
(defun cube (x)
(* x x x))
(defun p (x)
(format t "p ~f~%" x)
(- (* 3 x)
(* 4 (cube x))))
(defun sine (angle)
(if (not (> (abs angle) 0.1))
angle
(p (sine (/ angle 3.0)))))
By running (sine 12.15) we can see that p is called 5 times. How does the call sequence look:
(sine 12.15) (p (sine 4.05)) (p (p (sine 1.35))) (p (p (p (sine 0.45)))) (p (p (p (p (sine 0.15))))) (p (p (p (p (p (sine 0.05)))))) (p (p (p (p (p 0.05))))) ...
Clearly, p is called for as long as the division of the angle by 3 stays above 0.1; therefore, the runtime of this function is logarithmic, more specifically O(log3(n)). The space is logarithmic as well, because this is a linear recursion where each computation is a single recursive call (as opposed to tree recursion, where each computation splits to 2 or more calls).
Related posts:
May 26th, 2008 at 16:53
“Clearly, p is called for as long as the division of the angle by 3 stays above 1.0;”
0.1
May 26th, 2008 at 17:39
liwei:
Thanks for noticing. I’ve fixed the typo
July 23rd, 2008 at 17:18
Dear Eli,
I’m studying Exercise 1.14, and I wonder if it’s true that
ccgrows exponentially in number of steps. I found that the number of steps can be computed by thecc-stepsprocedure below.(define (sigma m n fun)
(define (iterate sum m n)
(if (< n m)
sum
(iterate (+ sum (fun n)) m (- n 1))))
(iterate 0 m (floor n)))
(define (cc-steps amount kinds-of-coins)
(if (= kinds-of-coins 1)
(+ 1 (* amount 2))
(+ 1
(ceiling (/ amount (first-denomination kinds-of-coins)))
(sigma 1
(ceiling (/ amount (first-denomination kinds-of-coins)))
(lambda (k)
(cc-steps
(- amount (* (first-denomination kinds-of-coins)
(- k 1)))
(- kinds-of-coins 1)))))))
This amounts to nested summations, one fewer than the number of kinds of coins; so with five kinds of coins, there are four summations. This is how it looks expanded out in Maxima code:
f(x) := (1
+ ceiling(x/50)
+ sum(1
+ ceiling((x-50*(i-1))/25)
+ sum(1
+ ceiling((x-50*(i-1)-25*(j-1))/10)
+ sum(1
+ ceiling((x-50*(i-1)-25*(j-1)-10*(k-1))/5)
+ sum(1
+ 2*(x-50*(i-1)-25*(j-1)-10*(k-1)-5*(l-1)),
l,
1,
ceiling((x-50*(i-1)-25*(j-1)-10*(k-1))/5)),
k,
1,
ceiling((x-50*(i-1)-25*(j-1))/10)),
j,
1,
ceiling((x-50*(i-1))/25)),
i,
1,
ceiling(x/50)));
Xis in the term of the innermost summation and also in the upper bound, so ignoring everything butx,xis addedxtimes, which isx^2. All four summations then result inx^5, orxto the power of the number of kinds of coins. This is polynomial growth.I plotted
x^5againstcc-stepswithxfrom 0 to 100, from 0 to 500, and from 0 to 1000, and found that the curves matched more closely each time (I can send you JPEGs if you send me your email address).Please let me know if you see I’m making a mistake somewhere, and thanks for this great blog!
Thomas
December 15th, 2008 at 17:51
Hi, Eli
I’m studying Exercise 1.14 and I think the time complexity could be calculated as follow:
let f(n) = count-change(n, 1), and then we can get the f(n) by
f(n) = f(n- 1) + count-change(n, 0) + 1
= f (n -1) + 1 + 1 = f(n-1) + 2
= f(n – 2) + 2 + 2
…..
= f(n – n) + 2 * n
= 2 * n + 1
time complexity is O(n)
and then we let the g(n) = count-change(n, 2), x = ceil(n / 5), we can get
the g(n) by
g(n) = f (n) + g(n – 5) + 1
= f(n) + f(n – 5) + g(n – 5 * 2) + 1 + 1
…..
= f(n) + f(n – 5) + … f(n – 5 * (x – 1)) + g(n – 5 * x) + x
as the time complexity of f(n) is O(n) , and the approximation of x is
n/5, so time complexity of g(n) is O(n) * n/5 + n/5, which is O(n^2).
By using the same way, we can get the complexity of count-change(n, k)
is n^k (k <=5)
April 10th, 2009 at 12:07
I have posted a solution, with proof, to Ex 1.14 here:
http://sicp.org.ua/sicp/Exercise1-14?action=AttachFile&do=view&target=countingcoins.pdf
There are some minor errors in that file, but I don’t think they affect the outcome.
October 4th, 2009 at 20:09
I believe Thomas is right. I do not have a rigorous proof, but I believe the following reasoning is easy enough to follow:
There is one way to make change with only 1 cent coins. This solution takes n steps to find, so it’s time complexity is O(n).
There are n/5 ways to make change for an amount n with 1 and 5 cent coins, because you can use between 1 and n/5 5 cent coins and add an appropriate number of 1 cent coins to obtain n. On average, an amount of n/2 remains for the 1 cent coins, meaning the algorithm takes ~n/2 steps to find that solution (for large n, the 1 cent steps vastly outnumber the 5 cent ones).
This then makes for a time complexity of O(n^2).
For other two cent combinations, the same reasoning holds:
There are ~n/10 ways to make changes with 1 and 10 cent coins. On average, these again take ~n/2 steps to find, again making for a time complexity of O(n^2).
There are ~n/10 ways to make changes with 5 and 10 cent coins. On average, these take ~(n/5)/2 steps to find, again making for a time complexity of O(n^2).
Now for the interesting bit:
How many ways are there to make change with 1, 5 and 10 cent coins?
There are n/10 possibilities for the number of 10 cent coins. On average, the remaining amount that needs to be changed is n/2. There are n/5 ways to fill an amount with 1 and 5 cent coins, as per our earlier calculation. That makes for n/10*(n/5)/2 combinations.
Each of these combinations leaves, on average, n/2 to be filled by 1 cent coins, so again n/2 steps are needed by the algorithm. Consequently, the time complexity of this solution is O(n^3).
This argument can be extended for any number of different coins and coin sizes. As a result, the time complexity of the algorithm for this particular set of coins is O(n^5)
February 9th, 2010 at 09:54
Hi,Eli
Here’s a solution about Ex 1.14.
First,a defination of the time complexity,’ how many times the procedure does under the worst situation .”
So,maybe like this,for 5 different kinds of coins,each will take n times under the worst situation .And then the time complexity is n^5.
Obviously,it’s not rigorous.But that’s what I’ve learned and known.
Please let me known if it’s wrong.Thanks so much.
May 17th, 2012 at 05:38
Here’s a proof that (cc n c) is theta(n^c) where c is the number of denominations of coins.
The proof needs one assumption and one lemma. The assumption is that the smallest coin denomination is 1, ie we always start with pennies. This ensures that (cc n c) is non-decreasing as a function of n. The lemma (easy to prove) is: if f(n) is monotonic and polynomial, and g(n) is theta(n), then f(g(n)) is theta(f(n)).
We’ll go by induction on c. The case c = 1 is clear.
So assume (cc n c-1) is theta(n^(c-1)). We need to show that (cc n c) is O(n^c) and omega(n^c).
Write n = qd + r where d is the largest denomination, q and r are non-negative, and r is less than d. Note that n uniquely determines q and r, and as functions of n, q is theta(n) and r is theta(1).
The main thing is that we can write (cc n c) as a really nice summation involving only c-1:
(cc n c) = the sum as i goes from 0 to q of (cc n-i*d c-1)
To see this, just keep plugging in the recursive definition for any term involving c: (cc n c) = (cc n c-1) + (cc n-d c) = (cc n c-1) + (cc n-d c-1) + (cc n-2d c) etc, until you have q+1 terms. The first q terms only involve c-1 and the q+1 term is (cc n-qd c), but since n-qd = r which is less than d, (cc n-qd c) = (cc n-qd c-1).
Now we’ll use the assumption that cc is non-decreasing to note that the terms of this summation are arranged from biggest to smallest.
In particular, the first term is the biggest. So (cc n c) is bounded above by (q+1) times the first term, which is (cc n c-1). But q is theta(n) and (cc n c-1) is theta(n^(c-1)) by induction. So it follows that (cc n c) is O(n^c).
Getting the lower bound is the tricky part. We’re going to take the first half of the summation as a lower bound, and we’ll see that we still have theta(n) terms, all of which are bounded below by a term that is theta(n^(c-1)).
So let q’ be the integer part of q/2. Take the first q’ terms of the summation. Since cc is non-decreasing, all those q’ terms are bounded below by the q’+1 term, which is (cc n-q’d c-1). So we get q’ * (cc n-q’d c-1) as a lower bound for (cc n c).
Note that n-q’d is sandwiched between n and n/2. So it’s theta(n). Applying the lemma and the induction hypothesis, we get that (cc n-q’d c-1) is theta(cc n c-1) = theta(n^(c-1)). And of course q’ = floor(q/2) is theta(q) = theta(n). So it follows that (cc n c) is omega(n^c), completing the proof.