[plt-scheme] HtDP Section 29 -- Abstract Running Time & Big-O

On Aug 24, 2009, at 1:47 PM, David Yrueta wrote:

> ... a quadratic equation which accepts the number of elements in  
> the list -- 1/2 n^2 + 1/2n -- and outputs abstract running times  
> (N=4; abstract running time = 10).  We took the abstract running  
> time as "on the order of n^2" because, as Eugene says, "we ignore  
> the coeeficients because, as n grows, they matter less and less."   
> Am I in the ballpark?

Yes, that's on the right track.  If Program A runs twice as fast (or  
ten times as fast) as Program B, you can make up the difference by  
running Program B on faster hardware, or a better operating system,  
or with a more-optimizing compiler, or something like that.  But if  
Program A runs in O(n) time and Program B in O(n^2) time, nothing you  
can do will make Program B consistently faster than Program A, short  
of changing the algorithm.

Now suppose your goal is to study algorithmic efficiency, and you're  
not interested in hardware, compiler optimizations, or operating  
systems.  By ignoring constant factors, the effects of hardware,  
compiler, and operating system disappear completely and you're left  
with only differences between algorithms.  It's like one of those  
pictures where there's a message written in blue dots, obscured by a  
lot of red dots: if you look at it through a red filter, the red dots  
disappear and you're left with a clear view of what you were  
interested in.

One can introduce ordering operators "<", ">", "<=", ">=", and "="  
into the space of functions.  (I'll keep the quotation marks, to  
distinguish these things from ordinary numeric ordering operators.)   
If function f, in the long run, is at most a constant factor larger  
than g, then we say f "<=" g or g ">=" f.  If f "<=" g and  
simultaneously g "<=" f, we say f "=" g, and that f and g have the  
same order of growth.  If f "<=" g but it's NOT true that g "<=" f,  
we say that f "<" g, i.e. that f grows strictly slower than g.  In  
fact, these operators act pretty much the way you expect except that  
they don't obey trichotomy, i.e. it's quite possible for particular  
functions f and g to satisfy none of "<", "=", nor ">".

It turns out that once you agree to ignore constant factors, you are  
forced to also ignore slower-growing additive terms, because (for  
example) n^2 "<=" n^2+n "<=" 2n^2 "=" n^2.  n^2+n, being pinched in  
between two things that are "equal", must be "equal" to both of  
them.  (This is intuitive reasoning, but it can also be made rigorous.)

Stephen Bloch
sbloch at adelphi.edu