Big-O notation

[Erik Max Francis]

Paul Moore wrote:

> Just to clarify this point a bit, the measure usually used in sorting
> is the number of swaps of two elements (or the number of comparisons -
> these are usually equivalent in terms of O() calculations).

That touches on a point I meant to address but forgot, which is that the
big-O notation can really refer to anything at all.  Usually it refers
to algorithm complexity (how much "stuff" needs to get done -- as you
rightly point out in the case of a sorting algorithm it would be the
number of compares), but it could apply to anything like numeric
multiplications, or even amount of memory used either by a static data
structure or an algorithm.

It's really just a method for expressing how complex "something" gets
for very large n (mathematically, as n -> oo).  What that something is
can vary from usage to usage.

-- 
 Erik Max Francis / max at alcyone.com / http://www.alcyone.com/max/
 __ San Jose, CA, USA / 37 20 N 121 53 W / &tSftDotIotE
/  \ Covenants without the sword are but words.
\__/ Camden
    Bosskey.net: Aliens vs. Predator 2 / http://www.bosskey.net/avp2/
 A personal guide to Aliens vs. Predator 2.