# SICP Exercise 1.15

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

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