Big-O notation

[David Eppstein]

In article <3ckgewva.fsf at morpheus.demon.co.uk>,
 Paul Moore <gustav at morpheus.demon.co.uk> wrote:

> But for quicksort you partition, and compare each element against the
> partitioning element. That's n comparisons against log(n) partitioning
> elements (each partitioning step halves the size of the chunks, so you
> do this log2(n) times). So the complexity is O(n*log(n)).
> 
> Disclaimer: This is all *very* rough, and from memory as well. But I
> hope it's enough that you get the idea.

This is not completely accurate, since each partition is not usually 
exactly in half.  My favorite version of the quicksort analysis is in 
the new Cormen-Leiserson-Rivest-Stein version of Intro to Algorithms:
number the items according to their eventual sorted positions, then item 
i is compared to item j exactly when the first pivot in the range i..j 
is either i or j, which occurs with probability 2/|i-j+1|. Sum up these 
probabilities for all i<j to get the expected number of comparisons and 
you get roughly 2 n H_n (harmonic numbers) = O(n log n).

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