Michael L Torrie torriem at chem.byu.edu
Sat Sep 1 15:44:28 EDT 2007

• Previous message (by thread): list index()
• Next message (by thread): list index()
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

---

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

---

• Previous message (by thread): list index()
• Next message (by thread): list index()
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

---

More information about the Python-list mailing list