CODEWITHSUNDEEP
pythonperformancesettime-complexitybig-o
Kyle Marcus Enriquez
Kyle Marcus Enriquez

Reputation: 118

Python - time complexity of not in set

I know the time complexity of checking if x in set is O(1) but what about if x not in set? Would that be O(1) still because set is similar to a dictionary?

Upvotes: 0

Views: 2053

Answers (2)

138
138

Reputation: 574

For more information on the time complexities of Python Data Structures please reference this https://wiki.python.org/moin/TimeComplexity.

From this it is shown that x in s performs O(1) on average and O(n) in worst case. So as pointed out by user2357112 x not in s is equivalent to not x in s which just negates the result of x in s and will have the same time complexity.

Upvotes: 1

user2357112
user2357112

Reputation: 281287

x not in some_set just negates the result of x in some_set, so it has the same time complexity. This is the case for any object, set or not. You can take a look at the place where the CPython implementation does res = !res; if you want.

Upvotes: 7

Related Questions