Most efficient solution?
Alexandre Fayolle
alf at leo.logilab.fr
Mon Jul 16 13:14:31 EDT 2001
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'?
Alexandre Fayolle
--
LOGILAB, Paris (France).
http://www.logilab.com http://www.logilab.fr http://www.logilab.org
Narval, the first software agent available as free software (GPL).
More information about the Python-list
mailing list