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

[andersk at mit dot edu]

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

--- Comment #13 from Anders Kaseorg <andersk at mit dot edu> ---
(In reply to Patrick J. LoPresti from comment #12)
> 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?

I should have been clearer: I’m saying it rules out quickselect with a
deterministic pivot selection rule that doesn’t inspect Θ(n) elements. 
Quickselect with randomized Θ(1) pivot selection would satisfy the
specification, as would quickselect with deterministic Θ(n) pivot selection by
median-of-medians or similar, but not quickselect with deterministic Θ(1) pivot
selection by taking the first element or similar.