[archives] [homepage]

Problem 1.15
Friday, August 23, 2019; ago; Download .md

SICP Exercise 1.15

The formula for calculating $$ \sin x $$ is:

$$ \sin x = 3 \sin \frac{x}{3} - 4 \sin^3 \frac{x}{3} $$

Applying the procedure to (sin 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))))) 

Clearly, the procedure is called 5 times.

For order of growth in space, we have the following:

  • a fixed space cost, each time p is applied to the recursive invocation of sine
  • the number of steps are fixed for each iteration

For every invocation of sin, the angle a is divided by 3. This new value is again divided until a reaches a terminating value (0.1 in this case). We can say that the number of steps varies logarithmically with a. Order of growth is $$\Theta \log(a)$$.