From: Joel Young (jdy_at_[hidden])
Date: 2004-03-03 13:36:20
From: David Abrahams <dave_at_[hidden]>
> Joel Young <jdy_at_[hidden]> writes:
>> From: Brian McNamara <lorgon_at_[hidden]>
>>> Like any quicksort, it's O(N^2), but the constant-factor costs here are
>> nlog(n) ?
> Average case: nlog(n)
> Worst case: n^2
Momentary brainfart O vs whp. Randomized quicksort IIRC is nlog(n) with
high probability (prob of bad case goes to zero at least as fast as 1/n).
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk