How to demonstrate bigO cost of algorithms?

[David Eppstein]

In article <WWwvc.4691$co6.821 at news02.roc.ny>,
 Matt <matt at themattfella.zzzz.com> wrote:

> Rusty Shackleford wrote:
> 
> > All help is welcome.
> 
> For quicksort, you should see ((n log(n))/runtime(n)) approach some 
> constant as you increase n.

Well, except that he's not using random pivots.  For the quicksort code 
he listed, if the input is already sorted, the behavior should be 
Theta(n^2).

-- 
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science