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


Boost list run by bdawes at, gregod at, cpdaniel at, john at