Graham Fawcett fawcett at teksavvy.com
Wed Sep 10 07:23:54 CEST 2003

eduardo.aguiar.developer wrote:

>>> You are wright to mistrust it ;-)
>>> Though 'f in list' looks harmless it itself is o(n) because there 
>>> seems to
>>> be a linear search (This is different whith 'f in dict' of course). 
>>> So your
>>> list comprehension is of o(n*n).
>>> Kindly
>>> Michael P
>> D'oh! Thanks, Michael, I *knew* I'd messed that up...
>> I'll repeat "list searches linear, dict lookups constant..." a hundred
>> times before bed tonight.
> I think you got something to repeat
> the night after also :-)
> "list searches linear, dict lookups
> log2(n)"

I'm willing to be wrong twice, honestly I am! But I'm pretty sure it's 
constant time. B-tree searches are log2(n), but dicts aren't trees.

Can't find a real reference, but the Timbot spoke here:

If I'm wrong on this one, I'll wear the Python Dunce Cap for a week, 
while repeating my corrected lessons!

Now if you'll excuse me, I have to get back to my repetitions... ;-)

and-if-i'm-wrong-a-third-time-this-week-i'll-eat-the-cap'ly yours,

-- G

More information about the Python-list mailing list