[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

Anders Kaseorg <andersk at mit dot edu> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |andersk at mit dot edu

--- Comment #11 from Anders Kaseorg <andersk at mit dot edu> ---
(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.

Sometimes expected running time on average-case inputs is studied, but
referring to that definitely requires more words.