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.

Exercise 1.14

Draw a tree of the count-change procedure.

!["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 subtracts the 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 change n Θ(n). The number of steps for the procedure is Θ(n²). As n gets larger the number of branches recalulated grows exponentially.

Exercise 1.15

1. How many times is the procedure p applied?
2. 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)))))

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

   The procedure p is called 5 times before the angle is <= the precision value.

2. 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 p calls, so it too must be logartihmic