stdcxx-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Anton Pevtsov" <>
Subject Re: Re: test for lib.alg.nth.element
Date Tue, 07 Feb 2006 16:37:49 GMT
Martin Sebor wrote:
> Sounds good. Could you please go ahead and file the issue?

New jira issue is created:

With best wishes,
Anton Pevtsov.

-----Original Message-----
From: Martin Sebor [] 
Sent: Sunday, February 05, 2006 04:09
Subject: Re: test for lib.alg.nth.element

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:

> 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?


View raw message