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