fawcett at teksavvy.com
Wed Sep 10 07:23:54 CEST 2003
>>> 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).
>>> 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
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... ;-)
More information about the Python-list