os.listdir

[Graham Fawcett]

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:
http://mail.python.org/pipermail/tutor/2002-August/016800.html

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