Menu

- Chapter 1 Distilled
- Introduction
- 1.1 - The Elements Of Programming
- Expressions
- Naming and the Environment
- Evaluating Combinations
- Defining New Functions
- The Substitution Model
- Exercises
- Predicates
- Conditional Expressions
- Example: Newton’s Method
- Functions as Black-Box Abstractions
- 1.2 - Procedures and the Processes They Generate
- Linear Recursion and Iteration
- Tree Recursion
- Orders of Growth
- Exponentiation
- Example: Testing For Primality
- 1.3 Higher Order Functions
- Project - Blackjack

- Chapter 2 Distilled
- Introduction
- Data Abstraction
- Everything From Nothing
- Abstractions In Clojure
- Clojure's Data Structures
- Data Abstraction, Revisited
- Escher
- Project - Escher
- Symbolic Data
- Representing Sets
- Huffman Encoding Trees
- Zippers

The previous examples illustrate that processes can differ considerably in the rates at which they consume computational resources. One convenient way to describe this difference is to use the notion of order of growth to obtain a gross measure of the resources required by a process as the inputs become larger

Let n be a parameter that measures the size of the problem, and let
`R(n)`

be the amount of resources the process requires for a problem
of size `n`

. In our previous examples we took `n`

to be the number for
which a given function is to be computed, but there are other
possibilities. For instance, if our goal is to compute an
approximation to the square root of a number, we might take `n`

to be
the number of digits accuracy required. For matrix multiplication we
might take `n`

to be the number of rows in the matrices. In general
there are a number of properties of the problem with respect to which
it will be desirable to analyze a given process. Similarly, `R(n)`

might measure the number of internal storage registers used, the
number of elementary machine operations performed, and so on. In
computers that do only a fixed number of operations at a time, the
time required will be proportional to the number of elementary machine
operations performed.

We say that $R(n)$ has order of growth $\Theta(f (n))$, written $R(n) = \Theta(f (n))$ (pronounced "theta of f of 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 $\Theta(n)$. We also saw that the space required grows as $\Theta(n)$. For the iterative factorial, the number of steps is still $\Theta(n)$ but the space is $\Theta(1)$ (ie constant).

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 $1000n^2$ steps and a process requiring $3n^2 + 10n + 17$ steps all have $\Theta(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 $\Theta(n)$ (linear) process, doubling the size will roughly double the amount of resources used.

For an exponential process, each increment in problem size will multiply the resource utilization by a constant factor.

We will examine algorithms whose order of growth is logarithmic, so that doubling the problem size increases the resource requirement by a constant amount.

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

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

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:

```
(defn cube [x]
(* x x x))
(defn p [x]
(- (* 3 x) (* 4 (cube x))))
(defn 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?