[Python-Dev] PEP 393 Summer of Code Project (original) (raw)

Terry Reedy tjreedy at udel.edu
Sat Aug 27 08:25:17 CEST 2011

On 8/26/2011 8:23 PM, Antoine Pitrou wrote:

I would only agree as long as it wasn't too much worse than O(1). O(log n) might be all right, but O(n) would be unacceptable, I think. It also depends a lot on actual measured performance

Amen. Some regard O(nn) sorts to be, by definition, 'worse' than O(nlogn). I even read that in an otherwise good book by a university professor. Fortunately for Python users, Tim Peters ignored that 'wisdom', coded the best O(n*n) sort he could, and then measured to find out what was better for what types and lengths of arrays. So not we have a list.sort that sometimes beats the pure O(nlog) quicksort of C libraries.

-- Terry Jan Reedy

More information about the Python-Dev mailing list