Big-O notation (was: Re: Python and Schools)

[Erik Max Francis]

Chad Netzer wrote:

> Also, one further class that is import to know is O( 2**N ), such as
> the
> brute-force solution to the "travelling salesman problem".  These are
> much, MUCH worse than O( N**2 ) algorithms, and even today can rarely
> be
> computed for problems sets much larger than 100 (whereas O( N**2 )
> problem sets can grow to thousands or perhaps even millions and still
> be
> practically solved).  Rather than computing "solutions" with these
> types
> of algorithms, it is required to instead come up with "close-enough"
> or
> "best guess" type algorithms that CAN be computed practically on large
> data sets.

Note also (I'm sure you know this, Chad, I'm just elaborating for the
general benefit of everyone reading), since big-O notation represents
the behavior of algorithm complexity as the number of elements tends
toward infinity, it means that only the "biggest" function counts. 
e.g., something that might scale as n (n + 1) = n^2 + n -- for instance,
having a collection of n elements and selecting all pairs i, j where i
!= j -- only is written as O(n^2), since as n -> oo, n^2 grows much
faster than n.

It also means that one doesn't bother distinction between logarithms
base 10, e, 2, etc.; O(ln n) ~ O(lg n) ~ O(lb n).  Similarly, O(2^n) ~
O(10^n) ~ O(e^n) too.

There's also amortized notation, where on average you'd expect a certain
type of behavior but occasionally it will be another.  For instance,
adding an element to the end of a dynamically resizing vector (like a
list in Python) is amortized O(1), since typically the operation will
take constant time, but occasionally (like when you're at the end of the
vector's capacity and it needs to be resized) it will take O(n). 
Amortized is when you expected it to take O(f(n)), but only about every
n operationss, so one calls it "amortized O(f(n)/n)"; in this case, the
worst case is O(n), which should only happen every n operations, so you
speak of "amortized O(n)" (n/n = 1).

As Roy Smith mentioned, this is not merely of academic interest,
although formally defining it takes knowledge of calculus.  It is
vitally important that you know the complexity of the algorithms you're
using and how they'll interrelate to avoid scalability problems.

-- 
 Erik Max Francis / max at alcyone.com / http://www.alcyone.com/max/
 __ San Jose, CA, USA / 37 20 N 121 53 W / &tSftDotIotE
/  \ I want a martini that could be declared a disaster area.
\__/ Capt. Benjamin "Hawkeye" Pierce
    Crank Dot Net / http://www.crank.net/
 Cranks, crackpots, kooks, & loons on the Net.