https://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968
Patrick J. LoPresti <lopresti at gmail dot com> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |lopresti at gmail dot com
--- Comment #10 from Patrick J. LoPresti <lopresti at gmail dot com> ---
Worth noting, perhaps, that the C++ standard does _not_ require O(n) worst-case
behavior for nth_element. The exact wording (C++11 section 25.4.2
[alg.nth.element] paragraph (3)) says:
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 (?)
Anyway, just because GCC falls back to an O(N log N) algorithm under some
circumstances does not necessarily mean it violates the C++ specification, as
long as that fallback only happens in log N of the cases or thereabouts.
Not that I am up for actually performing this complexity analysis.
