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 Thu, 02 Feb 2006 16:05:59 GMT
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. 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.

2006-02-02  Anton Pevtsov  <>

    * 25.nth.element.cpp (test_nth_element): update the upper bound
    value to more strict one.

With best wishes,
Anton Pevtsov

-----Original Message-----
From: Martin Sebor []
Sent: Wednesday, February 01, 2006 05:43
Subject: Re: test for lib.alg.nth.element

Anton Pevtsov wrote:

 >> The attached file contains my attempt to implement test for
 >> lib.alg.nth.element (I hadn't found any test for this algorithm in
 >> current version).

Excellent! Thank you!

I fixed a couple a copy ad paste mistakes and committed it here:
(I also reduced the number of loops to 256 to avoid stressing our
testing infrastructure too much  :)

 >> Here I used the hardcoded sequences to check that the algorithm works
 >> correctly and random-generated sequences to verify the complexity.

Good idea!  :)

 >> I set the upper bound for complexity to 2 * N * log N, but this may be

 >> not enough strict for large N (according to the standard the
 >> complexity should be "linear or average"). At the same time for small
 >> sequences the complexity is greater than N * log N.

That's definitely not strict enough for a linear algorithm (i.e., O(K *
N) with K << N). The problem, of course, is finding K, which I assume,
is why you chose K = 2 * log(N). However, K should be a constant and not
a function of N. We need to fix it. I'll leave it up to you to decide
whether you want to create an issue for it as a reminder to make sure we
revisit it after we've had some time to think about and discuss it, or
whether you want to fix it right away.

Thanks again!

View raw message