Introduction

The in operator in Python checks whether a value exists in a collection. Its time complexity depends entirely on the data structure: O(1) average for sets and dictionaries, O(n) for lists and tuples, and O(n) for strings (where n is the string length). Choosing the right data structure for membership testing is one of the most impactful performance decisions in Python code.

Time Complexity by Data Structure

List and Tuple: O(n)

Lists and tuples use sequential search. Python walks through each element and compares it to the target.

1numbers = [3, 7, 1, 9, 4, 6, 8, 2, 5, 0]
2
3# Python checks 3, then 7, then 1, ... until it finds 8
48 in numbers  # True — checked 7 elements
5
6# Worst case: element is last or not present
7-1 in numbers  # False — checked all 10 elements

1import timeit
2
3small = list(range(100))
4large = list(range(1_000_000))
5
6# O(n) — 10000x larger list takes ~10000x longer
7timeit.timeit(lambda: 99 in small, number=100_000)     # ~0.05s
8timeit.timeit(lambda: 999_999 in large, number=100)     # ~1.5s

Set and Dict: O(1) Average

Sets and dictionaries use hash tables. Lookup involves computing a hash and checking one (or a few) buckets.

1number_set = {3, 7, 1, 9, 4, 6, 8, 2, 5, 0}
2
3# Hash-based lookup — constant time regardless of size
48 in number_set  # True — O(1)
5-1 in number_set  # False — O(1)

1import timeit
2
3small_set = set(range(100))
4large_set = set(range(1_000_000))
5
6# O(1) — same speed regardless of size
7timeit.timeit(lambda: 99 in small_set, number=100_000)       # ~0.004s
8timeit.timeit(lambda: 999_999 in large_set, number=100_000)  # ~0.004s

For dictionaries, in checks keys by default:

1d = {"alice": 1, "bob": 2, "charlie": 3}
2
3"bob" in d           # True — O(1), checks keys
4"bob" in d.keys()    # True — O(1), same behavior
5"bob" in d.values()  # True — O(n), values have no hash table
62 in d               # False — checks keys, not values

String: O(n)

For strings, in performs substring search, not character lookup.

1text = "the quick brown fox jumps over the lazy dog"
2
3"fox" in text       # True — substring search
4"cat" in text       # False
5"quick brown" in text  # True — multi-character substring
6
7# Single character is also substring search
8"q" in text         # True

Python uses a combination of Boyer-Moore and Horspool algorithms for substring search, giving O(n/m) average case where n is the text length and m is the pattern length. Worst case is O(n*m) but this rarely occurs with real text.

Range: O(1)

Python 3's range objects support O(1) membership testing through arithmetic:

1r = range(0, 1_000_000_000)
2
3# O(1) — Python calculates (999_999_999 - 0) % 1 == 0
4999_999_999 in r  # True — instant
5
6# Also O(1) with step
7r = range(0, 100, 3)
815 in r   # True — (15 - 0) % 3 == 0 and 0 <= 15 < 100
916 in r   # False — (16 - 0) % 3 != 0

Converting List to Set for Repeated Lookups

If you perform multiple membership tests against the same collection, converting a list to a set pays off quickly.

1# BAD — O(n) per lookup, O(n*m) total
2allowed_users = ["alice", "bob", "charlie", "diana", ...]  # 10,000 users
3requests = [...]  # 100,000 requests
4
5for req in requests:
6    if req.user in allowed_users:  # O(n) each time
7        process(req)
8
9# GOOD — O(1) per lookup after O(n) conversion
10allowed_set = set(allowed_users)  # O(n) one-time cost
11
12for req in requests:
13    if req.user in allowed_set:  # O(1) each time
14        process(req)

The set conversion costs O(n) once. Each lookup is then O(1). For m lookups, total goes from O(n*m) to O(n + m).

The O(n) Worst Case for Sets

Set lookup degrades to O(n) when many keys hash to the same bucket (hash collision). This is rare with Python's built-in types but can happen with adversarial input or poorly implemented __hash__.

1# Pathological case — all objects hash to the same value
2class BadHash:
3    def __init__(self, value):
4        self.value = value
5    def __hash__(self):
6        return 42  # Every object has the same hash
7    def __eq__(self, other):
8        return self.value == other.value
9
10# All elements in one bucket — O(n) lookup
11bad_set = {BadHash(i) for i in range(10_000)}
12BadHash(9999) in bad_set  # O(n) — must scan the entire bucket

not in Operator

not in has the same time complexity as in. It simply negates the result.

5 not in [1, 2, 3]      # True — O(n)
5 not in {1, 2, 3}      # True — O(1)
"x" not in "hello"      # True — O(n)

Common Pitfalls

• Using a list for repeated membership tests: Checking x in large_list inside a loop is O(n) per check. Convert to a set first if you do more than a few lookups. The break-even point is typically 3-5 lookups.
• Checking in dict.values(): key in dict is O(1) because it checks keys. value in dict.values() is O(n) because values are not hashed. If you need fast value lookup, build a reverse mapping.
• Assuming in on a generator is efficient: x in generator consumes the generator element by element until it finds a match or exhausts the generator. This is O(n) and the consumed elements are gone.
• Confusing substring in with element in: For strings, "ab" in "abc" checks for a substring. For lists, "ab" in ["a", "b", "abc"] checks for an exact element match. These are different operations.
• Forgetting range is O(1): 1_000_000 in range(2_000_000) is instant in Python 3. In Python 2, range() returns a list (O(n)). Use xrange() in Python 2 for O(1) behavior.

Summary

• in on list/tuple: O(n) — sequential scan
• in on set/dict: O(1) average — hash table lookup
• in on str: O(n) — substring search using optimized algorithms
• in on range: O(1) — arithmetic membership test
• Convert lists to sets when doing repeated membership tests
• key in dict is O(1) but value in dict.values() is O(n)
• Python 3's range supports O(1) in checks; Python 2's range does not