stdcxx-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Martin Sebor <se...@roguewave.com>
Subject Re: test for lib.alg.nth.element
Date Sun, 05 Feb 2006 01:08:48 GMT
Anton Pevtsov wrote:
> Martin Sebor wrote:
>  > That's definitely not strict enough for a linear algorithm
>  > (i.e., O(K * N) with K << N)
> [...]
> 
> I exercised the nth_element algorithm with large random-generated
> sequnces and found that K is not great than 8.
> The attached patch sets the upper bound to 8 * N to avoid function of N
> there.

Okay, that's better. Applied thus:
http://svn.apache.org/viewcvs.cgi?rev=374954&view=rev

> The better way is to avoid such "magic"
> numbers at all, but for this purpose it is necessary to found the worst
> sequence for an algorithm.
> So I suggest to open the jira issue as a reminder that we need to
> investigate each algorithm to find the worst case for it and
> use the complexity on this worst sequence as the upper bound in tests.

Sounds good. Could you please go ahead and file the issue?

Thanks
Martin

Mime
View raw message