Free Structure and Interpretation of Computer Programs by Harold Abelson and Gerald Jay Sussman with Julie Sussman Page B

that
R
(
n
) has order of growth θ(
f
(
n
)), written
R
(
n
) = θ(
f
(
n
)) (pronounced “theta of
f
(
n
)”), if there are
positive constants
k
1 and
k
2 independent of
n
such that
    k
1
f
(
n
) ≤
R
(
n
) ≤
k
2
f
(
n
)
for any sufficiently large value of
n
. (In other
words, for large
n
, the value
R
(
n
) is sandwiched between
k
1
f
(
n
)
and
k
2
f
(
n
).)
    For instance, with the linear recursive process for computing
factorial described in section  1.2.1 the
number of steps grows proportionally to the input
n
. Thus, the
steps required for this process grows as θ(
n
). We also saw
that the space required grows as θ(
n
). For theiterative
factorial, the number of steps is still θ(
n
) but the space is
θ(1) – that is, constant. 36 Thetree-recursive Fibonacci computation requires
θ(
φ
n ) steps and space θ(
n
), where
φ
is the
golden ratio described in section  1.2.2 .
    Orders of growth provide only a crude description of the behavior of a
process. For example, a process requiring
n
2 steps and a process
requiring 1000
n
2 steps and a process requiring 3
n
2 + 10
n
+ 17 steps
all have θ(
n
2 ) order of growth. On the other hand, order of
growth provides a useful indication of how we may expect the behavior
of the process to change as we change the size of the problem. For aθ(
n
) (linear) process, doubling the size will roughly double the amount
of resources used. For anexponential process, each increment in
problem size will multiply the resource utilization by a constant
factor. In the remainder of section  1.2 we will examine two
algorithms whose order of growth islogarithmic, so that doubling the
problem size increases the resource requirement by a constant amount.

    Exercise 1.14.   Draw the tree illustrating the process generated by the
count-change
procedure of section  1.2.2 in making
change for 11 cents. What are the orders of growth of the space and
number of steps used by this process as the amount to be changed
increases?

    Exercise 1.15.   The sine of an angle (specified in
radians) can be computed by making use of the approximation
sin
x
≈
x
if
x
is
sufficiently small, and the trigonometric identity

    to reduce the size of the argument of
sin
. (For
purposes of this exercise an angle is considered “sufficiently
small” if its magnitude is not greater than 0.1 radians.) These
ideas are incorporated in the following procedures:

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

    a.  How many times is the procedure
p
applied when
(sine 12.15)
is evaluated?
    b.  What is the order of growth in space and number of steps (as a
function of 
a
) used by the process generated by the
sine
procedure when
(sine a)
is evaluated?

1.2.4  Exponentiation
    Consider the problem of computing the exponential of a given number.
We would like a procedure that takes as arguments a base
b
and a
positive integer exponent
n
and computes
b
n . One way to do this
is via the recursive definition
    b n
=
b
·
b
n
-1
b
0 = 1
    which translates readily into the procedure

    (define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))

    This is a linear recursive process, which requires θ(
n
) steps
and θ(
n
) space. Just as with factorial, we can readily
formulate an equivalent linear iteration:

    (define (expt b n)
  (expt-iter b n 1))

(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                (- counter 1)
                (* b product)))) 

    This version requires θ(
n
) steps and θ(1) space.
    We can compute exponentials in fewer steps by using successive
squaring. For instance, rather than computing
b
8 as
    b
· (
b
· (
b
· (
b
· (
b
· (
b
· (
b
·
b
))))))
we can compute it using