Re: [boost] [gil] Ideas to make my extension more generic?

From: Peter Dimov (pdimov_at_[hidden])
Date: 2007-04-29 14:04:36

Lubomir Bourdev wrote:
> John,
> 
> On 4/29/07 12:41 AM, "John Femiani" <JOHN.FEMIANI_at_[hidden]> wrote:
>> 
>> Lubomir,
>> Regarding your comment:
>> 
>>> I haven't thought much about this, but this is
>>> k-order statistic (in an array of numbers, find
>>> the K-th smallest one). There is an algorithm to do
>>> this in O(N). This would be rather useful, perhaps
>>> someone should put it in Boost?
>> 
>> It is part of the stl already: std::nth_element in the <algorithm>
>> header.
> 
> My understanding is that std::nth_element partially sorts the range,
> suggesting O(NlogN) running time. There are algorithms to return the
> n-th smallest element in an unordered list in O(N).

std::nth_element has (average) linear complexity.