Re: [boost] Re: FC++ -- reminder formal review ends today at midnightPST

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