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 randomgenerated
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.
Log:
20060202 Anton Pevtsov <antonp@moscow.vdiweb.com>
* 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 [mailto:sebor@roguewave.com]
Sent: Wednesday, February 01, 2006 05:43
To: stdcxxdev@incubator.apache.org
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:
http://svn.apache.org/viewcvs.cgi?rev=373968&view=rev
(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 randomgenerated 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!
Martin
