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

[David Eppstein]

In article <LhiA8.40883$8D3.1196292 at news1.tin.it>,
 Alex Martelli <aleax at aleax.it> wrote:

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

My impression is that precompiled can beat interpreted by as much as a 
factor of 100.  What is the N for which that beats an O(log N) factor?

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