Some optimization tale

[Stephan Diehl]

Tim Peters wrote:

[...]
> Finding a maximal element also requires exactly N-1 comparisons.
> 
> Finding a min and a max in separate steps then requires exactly 2*(N-1)
> comparisons, or roughly 2*N.  If you can look for a min and a max in the
> same step, it's possible to reduce that.  For example, once things get
> started, take sequence elements two at a time.  Compare them to each
> other, then compare the smaller only to the smallest so far, and the
> larger only to
> the largest so far.  This requires 3 compares overall per pair of input
> elements, so takes about 1.5*N total compares to find a min and a max.
> 
> Sorting (with a theoretically best-possible comparison-based algorithm)
> requires an average of log_base_2(N!) comparisons, across randomly ordered
> sequences of length N.  That's (very) roughly N * log_base_2(N)
> comparisons. log_base_2(N) is bigger than 2 most of the time <wink>, and
> that's why doing min() and max() can beat the pants off of sorting.

It never hurts to do some math :-)
Thanks for your insights

Stephan