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 $ x \(</span> by noting that <span>\)(x) x\(</span> when <span>\)x\(</span> is sufficiently small. For larger values of <span>\)x\(</span>, <span>\) 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 $ _3 x $ divisions. After that, to take \(1\) to a value less than \(0.1\), it takes \(3\) more divisions ($ {3} = 0.037037037037037035 \(<span>). This gives us a total of <span>\)( _3 x + 3 )\(</span> 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 <span>\)[_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)\).