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

[Alex Martelli]

David Eppstein wrote:
        ...
> 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.

Sure -- indeed, .append has amortized constant time characteristics
only in pretty recent Python releases (in practice one didn't notice, but
in theory amortized time didn't get quite linear until shortly ago).

> 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.

Again, true.  I believe C++'s standard library (and the STL it comes
from) is rather unique in being an abstract specification that does
include big-O performance constraints.


> 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.

No doubt -- for small-enough N.  Just as doublessly, there will be
an N above which the O(N) algorithm is preferable.  When you write
performance-sensitive code for such tasks, measuring is really the
only way to select the thresholds at which to switch or otherwise
tune your algorithms.


Alex