Newbie: finding the key/index of the min/max element

[David Eppstein]

In article <XthA8.40723$8D3.1190011 at news1.tin.it>,
 Alex Martelli <aleax at aleax.it> wrote:

> Of course not.  In performance issues, one must always distinguish
> between "big-O" ones, and ones that boil down to mere multiplicative
> constants.

Of course, in Python, understanding big-O performance can be a little 
tricky -- you need to know something about the implementation details.
For instance, a loop append()ing items to a list turns out to take 
constant average-time per append, in C-python, but one might imagine an 
implementation (like Java Vectors with a nonzero capacityIncrement) 
where the time per append grows linearly in the length of the vector.
And other very similar operations, like inserting to the front of the 
list, take linear rather than constant time, but one could imagine 
implementations where that is not true.

Also, in Python, there is a big performance gap between built-ins (or 
precompiled C functions in general) and interpreted code, which may 
override big-O considerations: e.g. if you want to find the median of a 
list, I'm pretty sure it would usually be better just to sort the list 
and return the middle item, instead of using a linear-time median 
finding algorithm, despite the nonlinear big-O time of a sort.

-- 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein at ics.uci.edu http://www.ics.uci.edu/~eppstein/