Python 3.0 - is this true?

Rhamphoryncus rhamph at
Sun Nov 9 09:26:38 CET 2008

On Nov 8, 10:14 pm, Kay Schluehr <kay.schlu... at> wrote:
> I guess building a multiset is a little more expensive than just O(n).
> It is rather like building a dict from a list which is O(k*n) with a
> constant but small factor k. The comparison is of the same order. To
> enable the same behavior as the applied sorted() a multiset must
> permit unhashable elements. dicts don't do the job.

Although it has a runtime of k*n, it is still O(n).  big-O notation
ignores constant factors, dealing only with scalability.

More information about the Python-list mailing list