Boost logo

Boost :

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

My Bad.

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).

Joel


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk