pythonsetordered-set

Does OrderedSet() still have a search parameter of O(1)?

I have heard that when you perform an in operator on a list it has to search through O(n) objects while if you do it on a set it has to search through O(1) objects. To see what I mean go here. Does this still apply to OrderedSet?

Solution

  • Which OrderedSet are you talking about? At this time (Python 3.8.3), there is not OrderedSet in the standard library.

    Typically, OrderedSet implementations will implement __contains__ by delegating to the underlying set. So it will have the algorithmic complexity you would expect.