Membership operators (in, not in) in Python - Time & Space Complexity

Time Complexity: Membership operators (in, not in)

O(n)

Understanding Time Complexity

When we use membership operators like in or not in, we check if a value exists inside a collection.

We want to know how the time it takes changes as the collection gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def check_membership(item, collection):
    if item in collection:
        return True
    else:
        return False

items = [1, 2, 3, 4, 5]
print(check_membership(3, items))

This code checks if item is inside collection and returns True or False.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each element in the collection one by one.
• How many times: Up to all elements in the collection until the item is found or the end is reached.

How Execution Grows With Input

As the collection gets bigger, the number of checks grows roughly the same as the number of items.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The work grows directly with the size of the collection.

Final Time Complexity

Time Complexity: O(n)

This means the time to check membership grows in a straight line as the collection gets bigger.

Common Mistake

[X] Wrong: "Membership checks always happen instantly no matter the collection size."

[OK] Correct: For lists or tuples without special structure, Python checks items one by one, so bigger collections take more time.

Interview Connect

Understanding how membership checks scale helps you write efficient code and explain your choices clearly in interviews.

Self-Check

"What if we changed the collection from a list to a set? How would the time complexity change?"