Re: test for lib.alg.nth.element

[Martin Sebor <se...@roguewave.com>]

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 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!
Martin