list index()

[Michael L Torrie]

Alex Martelli wrote:

> is the "one obvious way to do it" (the set(...) is just a simple and
> powerful optimization -- checking membership in a set is roughly O(1),
> while checking membership in a list of N items is O(N)...).

Depending on a how a set is stored, I'd estimate any membership check in
a set to be O(log N).  That's if it's stored in a tree of some kind,
which you'd need to fast finding.  Say a balanced binary tree.  Worst
case, you'd have to search half of the elements to find what you were
looking for.

> 
> 
> Alex