Exercise 1.15 in SICP requires us to find the order of growth in time and space of a procedure that approximates the value of $\sin x$ by noting that $\sin \left(x\right) \approx x$ when $x$ is sufficiently small. For larger values of $x$, $\sin x$ can be recursively calculated using the trigonometric identity

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

Here is the implementation from the book:

(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 first task is to calculate the number of times the procedure p is called for the invocation (sine 12.15). This is straightforward using the substitution rule:

(sine 12.15)
-> (p (sine (/ 12.15 3))
-> (p (sine 4.05))
-> (p (p (sine (/ 4.05 3))))
-> (p (p (sine 1.349999999999999)))
-> (p (p (p (sine (/ 1.349999999999999 3)))))
-> (p (p (p (sine .44999999999999996))))
-> (p (p (p (p (sine (/ .44999999999999996 3))))))
-> (p (p (p (p (sine .15)))))
-> (p (p (p (p (p (sine (/ .15 3)))))))
-> (p (p (p (p (p (sine .05))))))
-> (p (p (p (p (p 0.05)))))


In the last line of the partial derivation above, we hit the base case and are left with a stack of five p calls, with no more recursion. Generally, for any angle value $x$, the number of p calls here will be $[\log_3 x + 3]$. To understand why, note that, given an angle $x$, to reach $1$ by successively dividing by $3$ (which our sine implementation does), we will need $\log_3 x$ divisions. After that, to take $1$ to a value less than $0.1$, it takes $3$ more divisions ($\frac { \frac { \frac {1} {3} } {3} } {3} = 0.037037037037037035$). This gives us a total of $\left( \log_3 x + 3 \right)$ divisions, which corresponds to the number of times p is called. To account for angles which are not powers of three, we round that count to the nearest integer, resulting in $[\log_3 x + 3]$.

## Order of growth

It follows directly from the last paragraph that the space used by our sine procedure varies directly with the number of p calls, which we just established to be logarithmic in the angle $a$. To see it from another perspective, note that tripling the angle argument to sine only adds one to the number stacked calls to p. This is a tell-tale sign of a logarithmic order of growth. Therefore, the space consumed by sine is $\Theta \left( \log a \right)$.

Now to examine the order of growth of the number of steps involved in the calculation of (sine a), notice that there are as many divisions by $3$ as there are calls to p, followed by the same number of calculations within p (because p itself runs in constant time). Since the number of calls to p is $\Theta \left( \log a \right)$, the number of total steps in calculating (sine a) is an integer multiple of $\Theta \left( \log a \right)$, which is again $\Theta \left( \log a \right)$.