Solution to SICP Exercise 1.15

Structure and Interpretation of Computer Programs

Solution to Exercise 1.15:

Part a. Here’s the process of (sine 12.15).

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

There are clearly 5 applications of the p procedure.

Part b. We can see from the process above that the p procedure is applied for every power of 3.0 in angle. The order of growth in the number of steps is therefore Θ(log3n). Because the p procedures accumulate for every power of three, the growth of process in space is also Θ(log3n).

Advertisements