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).
Probabalistic 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 probabalistic methods right now.
Back to flipping out…
