python 3's adoption
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