Mailing-List: contact stdcxx-dev-help@incubator.apache.org; run by ezmlm
Precedence: bulk
Reply-To: stdcxx-dev@incubator.apache.org
Received-SPF: pass (asf.osuosl.org: domain of AntonP@moscow.vdiweb.com
 designates 195.210.189.132 as permitted sender)
Content-class: urn:content-classes:message
MIME-Version: 1.0
Content-Type: text/plain;
	charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
Subject: Re: Re: test for lib.alg.nth.element
Date: Tue, 7 Feb 2006 19:37:49 +0300
Message-ID: <4D6A8407B7AC6F4D95B0E55C4E7C4C62039D2B3A@exmsk.moscow.vdiweb.com>
Thread-Topic: Re: test for lib.alg.nth.element
Thread-Index: AcYp8DSJ0G6VICpGQk+CpybzlltR2AB3QqxQ
From: "Anton Pevtsov" <AntonP@moscow.vdiweb.com>
To: <stdcxx-dev@incubator.apache.org>

Martin Sebor wrote:
> Sounds good. Could you please go ahead and file the issue?

New jira issue is created:
http://issues.apache.org/jira/browse/STDCXX-138


With best wishes,
Anton Pevtsov.


-----Original Message-----
From: Martin Sebor [mailto:sebor@roguewave.com]=20
Sent: Sunday, February 05, 2006 04:09
To: stdcxx-dev@incubator.apache.org
Subject: Re: test for lib.alg.nth.element


Anton Pevtsov wrote:
> Martin Sebor wrote:
>  > That's definitely not strict enough for a linear algorithm  >=20
> (i.e., O(K * N) with K << N) [...]
>=20
> I exercised the nth_element algorithm with large random-generated=20
> 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=3D374954&view=3Drev

> The better way is to avoid such "magic"
> numbers at all, but for this purpose it is necessary to found the=20
> worst sequence for an algorithm. So I suggest to open the jira issue=20
> as a reminder that we need to investigate each algorithm to find the=20
> 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