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.
