From: Rene Rivera (grafikrobot_at_[hidden])
Date: 2007-03-17 11:50:31
Hervé Brönnimann wrote:
> Rene: What do you mean by "tighter complexity bounds"? Just curious,
I meant tighter guarantees of the complexity of the algorithm, in big O.
The customary quicksort is usually O(NlogN) on most sequences, but it
can be as high as O(N2). The quicksort variant I have has a guaranteed
worst case of O(NlogN). The price for that guarantee is a larger K
overall. Which if one is using objects for which the comparison is
expensive is a better trade off.
-- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk