Big-O notation

[Bjorn Pettersen]

> From: Ken R. [mailto:kriley1 at hotmail.com] 
> 
[...]
> It's been nearly forever since my compsci algorithms class so be
> gentle if I'm glaringly wrong :). 

ditto.

[...]
> No one decides what order an algorithm is, it is an inherant property 
> of the algorithm.

... which implies that it must have been _proven_ (it's a theoretical
system :-)

> If you execute quicksort on a wide variety of sample sets of different
> sizes then measure and plot the processor time vs sample size, it will
> approximate the graph of NlogN. Therefore the algorithm has order
> NLogN. The same will apply to bubble sort (order N^2), etc.
[...]

A commonly held belief, but as I said, it has to be proven, not
measured. Importantly, the statement entirely depends on the innocent
phrase "wide variety of sample [data]" (which would be valid if you were
trying to approximate the statistical mean of the algorithm). When
measuring, most people (should be?) are interested in _expected_
performance however, which means you need a "representable sample" (of
the domain), but even when well defined and acknowledged
programmers/scientists/... have historically proven to be highly
subjective when determining 'representable' <wink>. [Hint: you're
assuming you're only sorting random data].

-- bjorn