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:
http://svn.apache.org/viewcvs.cgi?rev=374954&view=rev
> 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?
Thanks
Martin