Processes and orders of growth

Lesson 01 gave us a way to name a process and seal it behind a contract, and a way to predict what value it returns — the substitution model. The instant we could name a process, a new question appeared: what does running it cost? This lesson separates a function's static definition from the dynamic process it generates when run, and shows that the same substitution trace whose value we already trust also reveals its shape — and the shape is the cost. We learn to read recursion vs. iteration off the trace, to spot the explosion of tree recursion, and to summarize all of it with orders of growth (Θ).

Book source

Maps to SICP §1.2 (Procedures and the Processes They Generate) — linear recursion vs. iteration, tree recursion, orders of growth, fast exponentiation, GCD, and probabilistic primality. We follow that arc; the JavaScript, the deferred-operation traces, and the cost tables are original.

Linear position

Prerequisite: Lesson 01 (the substitution model — a call reduces by repeated replacement; a function is a black box with a contract).
New capability: separate a function's definition from the process it generates, read the time and space cost off the substitution trace, classify processes with Θ orders of growth, and recognize when a small change in code (recursion → iteration, linear → logarithmic) collapses the cost.

The plan

Five moves. (1) Definition vs. process — the central distinction. (2) Linear recursion vs. linear iteration via factorial, reading the deferred-operations chain off the trace. (3) Tree recursion via Fibonacci, where the trace branches and work explodes. (4) Orders of growth Θ as the language of cost, with a cost table. (5) Algorithmic leverage: fast exponentiation Θ(log n), Euclid's GCD, and Fermat probabilistic primality. Then the pressure that forces lesson 03.

1 · Definition vs. process — the central distinction

A function definition is a static piece of text. The process it generates is the dynamic unfolding of evaluation when you call it — the sequence of substitution steps from lesson 01. These are different things, and the whole lesson rests on keeping them apart: two functions with identical results can generate processes with wildly different cost, and one function can generate different process shapes depending on how it is written. SICP's image: the definition is the recipe; the process is the cook actually doing it, and we want to predict how much counter space and time the cook needs.

2 · Linear recursion vs. linear iteration — factorial two ways

Compute n! two ways that return the same number but generate different processes.

// (a) recursive: n! = n * (n-1)!
function factR(n) { return n === 1 ? 1 : n * factR(n - 1); }

// (b) iterative: carry a running product as state
function factI(n) {
  function iter(product, counter) {
    return counter > n ? product : iter(product * counter, counter + 1);
  }
  return iter(1, 1);
}

Trace each with the substitution model and read the shape directly off the trace.

Worked example — the deferred-operations chain

factR(4)                       factI(4)  -- via iter(product, counter)
4 * factR(3)                   iter(1, 1)
4 * (3 * factR(2))             iter(1, 2)
4 * (3 * (2 * factR(1)))       iter(2, 3)
4 * (3 * (2 * 1))      <-peak   iter(6, 4)
4 * (3 * 2)                    iter(24, 5)
4 * 6                          24
24

recursive: the expression GROWS then shrinks      iterative: stays FLAT
 -- a chain of n deferred '*' ops builds up         -- no pending ops; just two
    (the interpreter must remember all of them)        numbers carried forward

The recursive trace grows a chain of n deferred multiplications before any of them runs — the interpreter must remember the whole chain, so space grows with n. The iterative trace never grows: the entire state is two numbers (product, counter), so space is constant. This visible difference — does the chain of pending operations grow, or stay flat? — is the difference between a recursive process and an iterative process.

Both do n multiplications, so both take linear time. They differ in space: factR is a linear recursive process — Θ(n) space for the deferred chain; factI is a linear iterative process — Θ(1) space, all the information lives in the variables it passes along. Note factI is still written with recursion (iter calls itself), but it generates an iterative process: the call is in tail position with no pending operation around it. The lesson 01 warning that "the shape of the reduction is a property of the process" is now made concrete.

3 · Tree recursion — Fibonacci and the explosion

Some processes branch. The naive Fibonacci definition calls itself twice:

function fib(n) { return n < 2 ? n : fib(n - 1) + fib(n - 2); }

Worked example — the call tree of fib(5)

                 fib(5)
            /              \
        fib(4)            fib(3)
       /     \           /     \
   fib(3)   fib(2)    fib(2)  fib(1)
   /   \    /   \     /   \
 f(2) f(1) f(1)f(0) f(1) f(0)
 / \
f(1)f(0)
-- fib(2) is recomputed THREE times; fib(3) TWICE. Nothing is remembered.

The number of nodes — hence the work — grows exponentially: roughly Θ(φⁿ) where φ ≈ 1.618. Worse, the same subproblems are recomputed from scratch over and over. fib(30) already makes over 2.6 million calls. The definition is three lines and obviously correct; the process is a disaster.

An iterative reformulation carries the last two values forward and runs in Θ(n) time, Θ(1) space — the same recursion-to-iteration move as factorial, but here it converts exponential to linear. The point stands: correctness is about the definition; cost is about the process, and you must reason about them separately.

4 · Orders of growth — the language of cost

We summarize a process's cost as how its resource use (time or space) scales with input size n, ignoring constant factors and lower-order terms. We write Θ(f(n)) to mean "grows like f(n)." This is deliberately coarse: it predicts how cost responds to scaling, which is what survives across machines and decades.

Order	Name	Example process	n=10 → n=100 means
Θ(1)	constant	look up an array element	no change
Θ(log n)	logarithmic	fast exponentiation; binary search	~3× the work
Θ(n)	linear	factR / factI; iterative fib	10× the work
Θ(n²)	quadratic	nested loop over pairs	100× the work
Θ(φⁿ)	exponential	naive fib	astronomically more

The table is the whole reason to care: moving a process one row up the table is usually worth far more than any constant-factor tuning. The next section shows the single most dramatic such move.

5 · Algorithmic leverage — log, GCD, and probabilistic primality

Fast exponentiation. Computing bⁿ by multiplying b together n times is Θ(n). But bⁿ = (b^n/2)² when n is even, so squaring halves the exponent each step — Θ(log n):

function expt(b, n) {                 // Theta(log n)
  if (n === 0) return 1;
  if (n % 2 === 0) { const h = expt(b, n / 2); return h * h; }
  return b * expt(b, n - 1);
}
// b^16 takes ~5 multiplications, not 16; b^1000 takes ~15, not 1000.

Euclid's GCD. gcd(a, b) = gcd(b, a mod b), bottoming out at gcd(a, 0) = a. The remainder shrinks fast (Lamé's theorem ties the step count to the Fibonacci numbers), giving Θ(log n):

function gcd(a, b) { return b === 0 ? a : gcd(b, a % b); }
// gcd(206, 40) -> gcd(40, 6) -> gcd(6, 4) -> gcd(4, 2) -> gcd(2, 0) = 2

Fermat primality. Some processes trade certainty for speed. Fermat's little theorem says if n is prime then for any a < n, aⁿ ≡ a (mod n). Test random a's: if any fails, n is definitely composite; if many pass, n is probably prime. Each test is Θ(log n) via fast exponentiation, and the error probability halves per independent test — a probabilistic algorithm, our first hint that "fast" and "certainly correct" can be deliberately traded against each other.

Common mistakes / failure modes

Equating "recursive code" with "recursive process"

factI is written recursively yet generates an iterative Θ(1)-space process. The shape that matters is whether pending operations accumulate around the call, not whether the source uses the word recursion.

Judging cost from the definition's length

Naive fib is three lines and exponential; iterative fib is longer and linear. Source size tells you nothing about the process; you must trace or analyze the unfolding.

Optimizing constants instead of order

Shaving a Θ(n²) loop's constant is dwarfed by finding a Θ(n log n) algorithm. Orders of growth say: change the row in the table before you polish within a row.

Forgetting recomputation in tree recursion

The explosion in fib is not the branching alone — it is recomputing identical subproblems. Remembering results (later: memoization, streams in lesson 13) is what tames it.

Checkpoint exercise

Try it

(1) Hand-trace factR(4) and factI(4) and mark, for each, the peak number of pending operations the interpreter must remember. (2) Without running it, state the time and space order of growth of this count_change-style function and say which kind of process it generates:

function f(n) { return n === 0 ? 1 : f(n - 1) + f(n - 1); }

Answers: (1) factR(4) peaks at 3 pending multiplications (the chain 4*(3*(2*factR(1)))) → linear recursive, Θ(n) space; factI(4) peaks at 0 pending operations (it only ever carries two numbers) → linear iterative, Θ(1) space. (2) f branches into two identical subcalls of size n-1, so the call tree has ~2ⁿ nodes: Θ(2ⁿ) time, a tree-recursive process; its space is Θ(n) (the depth of the deepest single path the interpreter is mid-way through). Note it does pure recomputation — the textbook explosion.

Where this points next

We can now read cost off the process and reach for the algorithm in the right row of the table. But look back at what we just wrote: sum-style accumulation in factI, the same accumulate-while-counting skeleton in iterative fib, the same "shrink the argument and recombine" pattern in expt and gcd. We keep re-typing the same control patterns with only the combining step changed. We have abstracted values (lesson 01) and now the shape of a process — but the recurring control skeletons themselves are crying out to be named and reused. The means of abstraction so far names a process; it cannot yet name a pattern across processes, because that would mean passing the varying piece — a function — as an argument. Lesson 03 grants exactly that: higher-order functions, which treat functions as first-class values you can pass in and return out, so a control pattern becomes a reusable abstraction. The repetition we just suffered is the pressure that forces it.

Takeaway

A function's definition is static text; the process it generates is the dynamic unfolding of evaluation, and the substitution trace from lesson 01 reveals not just the value but the shape — which is the cost. A linear recursive process (recursive factorial) grows a chain of deferred operations, costing Θ(n) space; a linear iterative process (iterative factorial) keeps its whole state in the variables it passes forward, costing Θ(1) space — and code written with recursion can still generate an iterative process. Tree recursion (naive Fibonacci) branches and recomputes subproblems, exploding to Θ(φⁿ). We summarize all of this with orders of growth Θ, and the practical law is to climb the cost table — Θ(n)→Θ(log n) via fast exponentiation and Euclid's GCD beats any constant-factor tuning, and Fermat's test shows you can even trade certainty for speed. Definition governs correctness; process governs cost — reason about them separately. The repeated control skeletons across all these functions are what force higher-order functions next.

Interview prompts

Distinguish a recursive process from an iterative process. (§2 — recursive: a chain of deferred operations accumulates (Θ(n) space); iterative: all state lives in passed-forward variables, nothing deferred (Θ(1) space) — independent of whether the source uses recursion.)
Why is naive Fibonacci exponential, and what fixes it? (§3 — it branches into two subcalls and recomputes identical subproblems (Θ(φⁿ)); carry the last two values iteratively (or memoize) for Θ(n).)
What does Θ(f(n)) mean and why ignore constants? (§4 — how resource use scales with input size, dropping constants and lower-order terms; it predicts response to scaling, which survives across machines, and changing the order dominates constant tuning.)
How does fast exponentiation reach Θ(log n)? (§5 — b^n = (b^(n/2))² for even n, so squaring halves the exponent each step instead of decrementing it.)
Explain Euclid's GCD and its order of growth. (§5 — gcd(a,b)=gcd(b, a mod b) until b=0; the remainder shrinks fast (Lamé), giving Θ(log n).)
What is a probabilistic algorithm, illustrated by Fermat's test? (§5 — it trades certainty for speed: random witnesses give "definitely composite" or "probably prime," with error halving per independent test, each test Θ(log n).)
Can a function written with recursion generate an iterative process? (§2 — yes: iterative factorial's iter calls itself in tail position with no pending operation, so state stays flat (Θ(1) space) — an iterative process despite recursive syntax.)