python 3's adoption

Paul Rubin no.email at nospam.invalid
Thu Jan 28 01:30:40 CET 2010


Jonathan Gardner <jgardner at jonathangardner.net> writes:
> You're referring to the O(N**2) bit, right? I am sure he knew it was O
> (N*log(N)), which is still worse than O(N) for key.

It's O(n log n) for both key and cmp.  key is usually more convenient
and usually gives a constant-factor speedup (DSU pattern), but it uses
more memory and there are some types of orderings that it can't handle
without a bunch of contortion.



More information about the Python-list mailing list