[Bug libstdc++/35968] nth_element fails to meet its complexity requirements

[lopresti at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968

--- Comment #12 from Patrick J. LoPresti <lopresti at gmail dot com> ---
(In reply to Anders Kaseorg from comment #11)
> (In reply to Patrick J. LoPresti from comment #10)
> > Complexity: Linear on average.
> > 
> > It is not obvious (to me) what distribution the "on average" refers to. All
> > permutations of input with equal probability, I suppose (?)
> 
> Expected running time is typically measured over the random choices (if any)
> made internally by the algorithm, not over a random input distribution.  For
> example, quickselect with random pivot selection would satisfy this, but not
> quickselect with deterministic pivot selection.

I am familiar with the usual algorithmic complexity definitions.

So, just to be clear... Your assertion is that the C++ standards committee
adopted a specification that rules out a deterministic implementation?