Orders of Growth
An order of growth is a measurement of a process as the problem domain changes. A process with a growth θ(n²) is said to grow exponentially with each increase of n.
Draw a tree of the
![“Exercise 1.14”][png1.14] [png1.14]: /assets/img/sicp/1.14.png “Exercise 1.14”
Each node represents a call to the
cc procedure. The
left operand is the amount of change and the right operand is the number
of coins. From every node there are two branches, the right branch
first-denomination from the amount of change, and the
left branch reduces the number of coins. Notice
(cc 6 1) is the
largest recalculated node.
The order of growth for the space is proportional to the amount of
n Θ(n). The number of steps for the procedure is Θ(n²). As
gets larger the number of branches recalulated grows exponentially.
- How many times is the procedure
- What is the order of growth?
;;EXERCISE 1.15 (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)))))
The procedure p is continuously applied until the angle is less than or equal to the explicit precision value 0.1
12.15 / 3.0 = 4.05 ; (p (sine 4.05)) 4.05 / 3.0 = 1.349 ; (p (p (sine 1.349))) 1.349 / 3.0 = .4499 ; (p (p (p (sine .4499)))) .4499 / 3.0 = .15 ; (p (p (p (p (sine .15))))) .15 / 3.0 = 4.99e-2 ; (p (p (p (p (p (sine 4.99e-2))))))
pis called 5 times before the angle is <= the precision value.
The number of steps for (sine a) = Θ(log a) The size of space for (sine a) = Θ(log a)
Note: My math skills are poor. but I think the number of steps are logarithmic because as ‘a’ grows in size the number of steps get smaller. Similarly, the space is related to the number of
pcalls, so it too must be logartihmic