3 Mar
2004
3 Mar
'04
6:36 p.m.
From: David Abrahams <dave@boost-consulting.com>
Joel Young <jdy@cs.brown.edu> writes:
From: Brian McNamara <lorgon@cc.gatech.edu>
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