Andy Armstrong andy at hexten.net
Tue Mar 3 13:22:08 GMT 2009

On 3 Mar 2009, at 12:57, Paul Makepeace wrote:
>> Think mainly about algorithm choice at write time - O(NlogN) always  
>> beats
>> O(N^2).
> It beats it only when the constant factors cancel. Often nlogn algos
> have larger constant factors e.g. owing to simply more ops in the
> process, so only start to win on larger n. IIRC Knuth says simple
> sorts beat quicksort often up to n=1000, which in many scripting
> scenarios is fair percentage of problems. (Not that anyone doesn't use
> 'sort' in perl but rather that going to the work of getting a lower
> order algo needs justification in terms of expected large datasets,
> and, realistically perf testing.)

Yeah, excuse the sloppy generalisation :)

Andy Armstrong, Hexten

More information about the london.pm mailing list