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?
