[plt-scheme] Math prerequisites for SICP

From: Prabhakar Ragde (plragde at uwaterloo.ca)
Date: Thu Feb 12 10:34:49 EST 2009

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


Posted on the users mailing list.