Complexity of *in* operator in Python

python time-complexity
Sajad Rastegar picture Sajad Rastegar · Dec 14, 2012 · Viewed 56.1k times · Source

What is the complexity of the in operator in Python? Is it theta(n)?

Is it the same as the following?

def find(L, x):
   for e in L:
       if e == x:
           return True
   return False

L is a list.

Answer

Andrew Clark picture Andrew Clark · Dec 14, 2012

The complexity of in depends entirely on what L is. e in L will become L.__contains__(e).

See this time complexity document for the complexity of several built-in types.

Here is the summary for in:

  • list - Average: O(n)
  • set/dict - Average: O(1), Worst: O(n)

The O(n) worst case for sets and dicts is very uncommon, but it can happen if __hash__ is implemented poorly. This only happens if everything in your set has the same hash value.

Related questions

How can you profile a Python script?

Project Euler and other coding contests often have a maximum time to run or people boast of how fast their particular solution runs. With Python, sometimes the approaches are somewhat kludgey - i.e., adding timing code to __main__. What …

Read More
Find common substring between two strings

I'd like to compare 2 strings and keep the matched, splitting off where the comparison fails. So if I have 2 strings - string1 = apples string2 = appleses answer = apples Another example, as the string could have more than one word. string1 = apple …

Read More
How efficient/fast is Python's 'in'? (Time Complexity wise)

In Python, what is the efficiency of the in keyword, such as in: a = [1, 2, 3] if 4 in a: ...

Read More