Today’s post is just a brief overview of Section 1.2, but don’t worry: I’ll be covering the (numerous) exercises soon. Section 1.2 covers a lot of ground in a little space. It introduces the ideas of recursive processes (both linear- and tree-recursive processes, a distinction that was new to me, but blindingly obvious in hindsight) and iterative processes (via tail-recursion), Big O analysis (though it doesn’t call it that), and mentions probabilistic methods in passing. I was a bit surprised at the early introduction of Big O; even though I consider it one of the more important things I learned in school, my intro CS course didn’t cover it until the end of the quarter, and the coverage was hardly in-depth.

#### Linear vs. Tree Recursion

This one is actually pretty straightforward: any time you only need to recurse once on each pass of the process, you’ve got linear recursion; if you need to recurse multiple times, you’ve got tree recursion.

#### Big O Analysis

SICP calls it
order of growth.
The basic concept is to analyze your algorithm/process/whatever in terms
of one aspect (typically time or space) and determine how that aspect
grows with respect to some aspect of the input (typically, the number or
size); think limits
from math class. For instance, the running time of
BubbleSort grows
proportionally to the square of the length of the array/list being
sorted, so its Big O is *O(n2)*.

#### Probabilistic Methods

The basic idea is that often a tight-enough approximation, which isn’t even all that tight in a lot of cases, is just as good as an exact answer, and a lot cheaper to compute. There’s a lot of ongoing research concerning probabilistic methods right now.

Back to flipping out…