A Sort Optimization Technique: decorate-sort-dedecorate
Joachim Durchholz
jo at durchholz.org
Tue Aug 29 14:01:19 EDT 2006
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
More information about the Python-list
mailing list