[Tutor] For - if - else loop; print selective output

[Oscar Benjamin]

On 25 October 2012 21:16, eryksun <eryksun at gmail.com> wrote:
> On Thu, Oct 25, 2012 at 3:46 PM, Prasad, Ramit
> <ramit.prasad at jpmorgan.com> wrote:
>>
>> Do you happen to know offhand if there is a difference between
>> `in <list>` vs. `in <tuple>` vs. `in <set>`?
>
> The "in" comparison (__contains__ method) is equivalent for list and
> tuple. It has to search through the sequence item by item, which makes
> it an O(n) operation. On the other hand, a set/dict uses the hash() of
> an object to map it to a known location in a table (performance
> degrades if there are many collisions). On average, you can check if a
> set/dict contains an item in constant time, i.e. O(1). The amortized
> worst case is O(n).

Why do you say "*amortized* worst case"? Is there an occasional worse
than O(n) operation that is insignificant when amortised?

At first I assumed that was a slip of the tongue but you generally
seem to know an incredible amount about the implementation of CPython,
so now I'm curious.


Oscar