SICP. 1.2.3
2022-12-12 Mon
This section of SICP introduces the concept of order of growth. A concept used ``to obtain a gross measure of the resources required by process as the inputs become larger''.
The order of growth of a linear recursive process — like that provided by the first example of process to compute factorial at p. 32 — is \(\Theta(n)\) in time as well as in space.
The order of growth of a linear iterative process — like that provided by the second example of process to compute factorial at p. 34 — is \(\Theta(n)\) in time, but \(\Theta(1)\) in space.
The tree-recursive process to compute Fibonacci (p. 37) required \(\Theta(\varphi^n)\) and spacee \(\Theta(n)\), where \(\varphi\) is the golden ratio.
Exercise 1.14
Exercise:
Draw the tree illustrating the process generated by the count-change procedure of 1.2.2 in making change for 11 cents. What are the orders of growth of the space and number of steps used by this process as the amount to be changed increases?
Answer:
Analogously to what shown at page 38 with respect to fib, we can
represent tree generated by count-change in the following way:
(count-change 11)
(cc 11 5)
/ \
(cc 11 4) (cc - 39 5)
/ \ \
(cc 11 3) (cc -14 4) 0
/ \ \
(cc 11 2) (cc 1 3) 0
/ \ / \
(cc 11 1) (cc 6 2) (cc 1 2) (cc -9 3)
___| /\____ |_____ \
___/ | | | |____ \_______ \_____
| | | \ | | |
(cc 11 0) (cc 10 1) (cc 6 1) (cc 1 2) (cc 1 1) (cc -4 2) 0
___/ ____/ | /\ |\ |_________ \__________
_____/ ___| / / \ | \_____ \_______ |______ |
| | / / | | | | | |
0 (cc 10 0) (cc 9 1) (cc 6 0) (cc 5 1) (cc 1 1) (cc -4 2) (cc 1 0) (cc 0 1) 0
/ /\ / / \ |\____ \ | |
__/ __/ \ / / \ | \___ \_____ | |
| / | | / \ | | | | |
0 (cc 9 0) (cc 8 1) 0 (cc 5 0) (cc 4 1) (cc 1 0) (cc 0 1) 0 0 1
| /\ | |\__ \ |
| / \ | | \ \ |
0 (cc 8 0) (cc 7 1) 0 (cc 4 0) (cc 3 1) 0 1
| /\ | /\
| / \ | / \
0 (cc 7 0) (cc 6 1) 0 (cc 3 0) (cc 2 1)
| /\ | /\
| / \ | / \
0 (cc 6 0) (cc 5 1) 0 (cc 2 0) (cc 1 1)
/ /\ / /\
/ / \ | / \
0 (cc 5 0) (cc 4 1) 0 (cc 1 0) (cc 0 1)
| /\ | |
| / \ | |
0 (cc 4 0) (cc 3 1) 0 1
| /\
| / \
0 (cc 3 0) (cc 2 1)
| /\
| / \
0 (cc 2 0) (cc 1 1)
| /\
| / \
0 (cc 1 0) (cc 0 1)
| |
0 1
This looks like a tree recursive processe like that of fib. And
In general, the number of steps required by a tree-recursive process will be proportional to the number of nodes in the tree, while the space required will be proportional to the maximum depth of the tree (p.39).
So I'm inclined to say the order of growth in time is \(\Theta(n^2)\) and the order of growth in space is \(\Theta(n)\). After having had a look around, though, the situation seems more controversial than it prima facie seemed… I'll try to go back to this at a future time.
Exercise 1.15
Exercise:
The sine of an angle (specified in radians) can be computed by making use of the approximation \(\sin x \approx x\) if \(x\) is sufficiently small, and the trigonometric identity
\(\sin x = 3 \sin \frac{x}{3} - 4 \sin^3 \frac{x}{3}\)
to reduce the size of the argument of \(\sin\). (For purposes of this exercise an angle is considered ``sufficiently small'' if its magnitude is not greater than 0.1 radians.) These ideas are incorporated in the following procedures:
(define (cube x) (* x x x)) (define (p x) (- (* 3 x) (* 4 (cube x)))) (define (sine angle) (if (not (> (abs angle) 0.1)) angle (p (sine (/ angle 3.0)))))
- How many times is the procedure p applied when
(sine 12.15)is evaluated?- What is the order of growth in space and number of steps (as a function of
a) used by the process generated by thesineprocedure when(sine a)is evaluated?
Answer:
(defun cube (x) (* x x x)) (defun p (x) (- (* 3 x) (* 4 (cube x)))) (defun sine (angle) (if (not (> (abs angle) 0.1)) angle (p (sine (/ angle 3.0))))) (sine 12.15) ;; -0.39980345741334 (p (sine (/ 12.15 3.0))) (p (sine 4.05)) (p (p (sine (/ 4.05 3.0)))) (p (p (sine 1.3499999999999999))) (p (p (p (sine (/ 1.3499999999999999 3.0))))) (p (p (p (sine 0.44999999999999996)))) (p (p (p (p (sine (/ 0.44999999999999996 3.0)))))) (p (p (p (p (sine 0.15))))) (p (p (p (p (p (sine (/ 0.15 3.0))))))) (p (p (p (p (p (sine 0.049999999999999996)))))) (p (p (p (p (p (sine 0.049999999999999996)))))) (p (p (p (p (p 0.049999999999999996))))) (p (p (p (p (- (* 3 0.049999999999999996) (* 4 (cube 0.049999999999999996))))))) (p (p (p (p 0.1495)))) (p (p (p 0.4351345505))) (p (p 0.9758465331678772)) (p -0.7895631144708228) (- -2.3686893434124685 -1.9688858859991285) -0.39980345741334
- We can see that procedure
pis applied five times. I tentatively thought that the order of growth in space and time was O(n).
However I've looked around at other people's solutions and that is not right. The order of growth is better than linear; it's logarithmic, O(log(n)); more specifically O(log3(n)). I definitively need to revive my math skills, hoping they still exist somewhere.
This was one of the most intuitive explanations I've found of why the order of growth is what it is: ``the amount of times
pis evaluated is incremented by one for every tripling ofa. […] As for the order of growth regarding space, it should be the same as for the number of steps, because for each additional step, there is exactly one more function call that the system must keep track of''. (https://www.timwoerner.de/posts/sicp/exercises/1/15/)