commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Ted Dunning <ted.dunn...@gmail.com>
Subject Re: [math] speeding up percentile based statistics
Date Thu, 23 Sep 2010 20:38:01 GMT
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.

On Thu, Sep 23, 2010 at 11:57 AM, Luc Maisonobe <Luc.Maisonobe@free.fr>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.
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message