Python 3.0 - is this true?

Kay Schluehr kay.schluehr at gmx.net
Sun Nov 9 12:51:42 CET 2008


On 9 Nov., 09:26, Rhamphoryncus <rha... at gmail.com> wrote:
> 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.

You are right. I remembered this short after my posting was sent.



More information about the Python-list mailing list