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
