Most efficient solution?
Aahz Maruch
aahz at panix.com
Mon Jul 16 14:25:49 EDT 2001
In article <slrn9l68fa.o6r.alf at leo.logilab.fr>,
Alexandre Fayolle <alexandre.fayolle at logilab.fr> wrote:
>On 16 Jul 2001 09:18:40 -0700, Aahz Maruch <aahz at panix.com> wrote:
>>Alexandre Fayolle <alexandre.fayolle at logilab.fr> wrote:
>>>
>>>I was referring to the inner loop. n is the number of elements in B
>>>(or of keys in C). 'item in B' is O(n), and 'C.has_key(item)' is O(log(n)).
>>>You still have to multiply by len(A) for the whole program.
>>
>>That's functionally incorrect. Except under severely degraded
>>conditions, C.has_key(item) is O(n).
>
>I'm pretty sure I was wrong, but are you sure you are not too? ;o)
>Should it not read: 'C.has_key(item) is constant'?
<smacks head>
--
--- Aahz <*> (Copyright 2001 by aahz at pobox.com)
Hugs and backrubs -- I break Rule 6 http://www.rahul.net/aahz/
Androgynous poly kinky vanilla queer het Pythonista
Fortune cookie: Watch your relations with other people carefully, be reserved.
More information about the Python-list
mailing list