Gabriel Genellina schrieb: > At Tuesday 29/8/2006 07:50, Joachim Durchholz wrote: > >> Wikipedia says it's going from 2NlogN to N. If a sort is massively >> dominated by the comparison, that could give a speedup of up to 100% >> (approximately - dropping the logN factor is almost irrelevant, what >> counts is losing that factor of 2). > > In fact it's the other way - losing a factor of 2 is irrelevant, > O(2N)=O(N). The logN factor is crucial here.
That's just a question of what you're interested in. If it's asymptotic behavior, then the O(logN) factor is a difference. If it's practical speed, a constant factor of 2 is far more relevant than any O(logN) factor. (I'm not on the list, so I won't see responses unless specifically CC'd.) Regards, Jo -- http://mail.python.org/mailman/listinfo/python-list