commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Luc Maisonobe <>
Subject Re: [math] speeding up percentile based statistics
Date Thu, 23 Sep 2010 23:13:27 GMT
Le 23/09/2010 22:38, Ted Dunning a écrit :
> If you use the median of three or five randomly selected points, the worst
> case/average case distinction is not going to come up.  You could even use
> the first, middle, end and two randomly selected points if you get nutty
> about it.

I intended to use median of three as it is a classical strategy. Of
course, Musser's "median of three killer" is always possible, but we
could wait for users complaints before handling it ...


> On Thu, Sep 23, 2010 at 11:57 AM, Luc Maisonobe <>wrote:
>> Partition-based algorithms are O(n) in expected time but not in worst
>> case time. If end users ask for it later, we could improve again by
>> adding the Musser's introselect that guarantees O(n) behavior even in
>> worst case.

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message