Python 3.0 - is this true?

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


On Nov 8, 10:14 pm, Kay Schluehr <kay.schlu... at gmx.net> 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