[plt-scheme] Math prerequisites for SICP
Thomas Chust wrote:
> to understand the big O notation you only need to know what a limit is
> in the mathematical sense and you need some measure for the cost of a
> computation, for example the number of operations of a certain kind
> that have to be performed.
Limits are not necessary to understand big-O notation. In fact, I would
argue that limits are the wrong way to deal with big-O notation, because
worst-case running times are discrete functions (since the "size" of the
input is typically an integer) and contain an extra quantifier ("for all
inputs of size n").
Limits can help in some of the manipulations needed to justify certain
claims made with O-notation, for example that an + b log n is O(n).
But the larger stumbling block is, as Thomas writes, "some measure for
the cost of a computation". HtDP presents a clear enough semantic model
that one can count steps. I can't remember if SICP does. --PR