Archives


« Prev: SICP section 1.2.2

» Next: The end of the road for ESMS


SICP section 1.2.3

June 28th, 2007 at 5:50 am

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

This entry was posted on Thursday, June 28th, 2007 at 5:50 am and is filed under SICP. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

3 Responses to “SICP section 1.2.3”

  1. liwei Says:
    May 26th, 2008 at 4:53 pm

    “Clearly, p is called for as long as the division of the angle by 3 stays above 1.0;”

    0.1

  2. eliben Says:
    May 26th, 2008 at 5:39 pm

    liwei:
    Thanks for noticing. I’ve fixed the typo

  3. Thomas Says:
    July 23rd, 2008 at 5:18 pm

    Dear Eli,

    I’m studying Exercise 1.14, and I wonder if it’s true that cc grows exponentially in number of steps. I found that the number of steps can be computed by the cc-steps procedure 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)));

    X is in the term of the innermost summation and also in the upper bound, so ignoring everything but x, x is added x times, which is x^2. All four summations then result in x^5, or x to the power of the number of kinds of coins. This is polynomial growth.

    I plotted x^5 against cc-steps with x from 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

Leave a Reply