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?"

Practice

1. What does the in operator do in Python?

easy

A. Creates a new collection

B. Adds a value to a collection

C. Removes a value from a collection

D. Checks if a value exists inside a collection

Solution

1. Step 1: Understand the purpose of in

   The in operator is used to check if a value is present inside a collection like a list, string, or tuple.

2. Step 2: Compare with other options

   Options A, B, and C describe actions unrelated to membership checking.

3. Final Answer:

   Checks if a value exists inside a collection -> Option D

4. Quick Check:

   in means membership check [OK]

Hint: Remember: in means 'is inside' [OK]

Common Mistakes:

• Confusing in with adding or removing items
• Thinking in changes the collection
• Mixing in with comparison operators

2. Which of the following is the correct syntax to check if the string 'apple' is NOT in the list fruits?

easy

A. if 'apple' not in fruits:

B. if 'apple' not fruits:

C. if not 'apple' fruits:

D. if 'apple' !in fruits:

Solution

1. Step 1: Recall correct syntax for not in

   The correct syntax to check absence is value not in collection.

2. Step 2: Evaluate each option

   if 'apple' not in fruits: matches correct syntax. if 'apple' not fruits: misses in. if not 'apple' fruits: misses in. if 'apple' !in fruits: uses invalid operator !in.

3. Final Answer:

   if 'apple' not in fruits: -> Option A

4. Quick Check:

   Use not in as two words [OK]

Hint: Use not in as two words, no symbols [OK]

Common Mistakes:

• Writing !in instead of not in
• Omitting in after not
• Using not 'value' in which is valid but less clear

3. What is the output of this code?

letters = ['a', 'b', 'c']
print('d' in letters)
print('a' not in letters)

medium

A. True\nTrue

B. False\nTrue

C. False\nFalse

D. True\nFalse

Solution

1. Step 1: Check if 'd' is in the list

   'd' is not in ['a', 'b', 'c'], so 'd' in letters is False.

2. Step 2: Check if 'a' is not in the list

   'a' is in the list, so 'a' not in letters is False, so print('a' not in letters) prints False.

3. Final Answer:

   False False is incorrect because the second print outputs False, but the first print outputs False, so the correct output is False False which matches False\nFalse.

4. Quick Check:

   'd' in letters = False, 'a' not in letters = False [OK]

Hint: Check each membership separately [OK]

Common Mistakes:

• Assuming 'd' is in the list
• Mixing up in and not in results
• Confusing True/False outputs

4. Find the error in this code snippet:

items = ['pen', 'pencil', 'eraser']
if 'pen' not items:
    print('Pen is missing')

medium

A. Incorrect print statement syntax

B. Wrong list name

C. Missing in after not

D. No error, code is correct

Solution

1. Step 1: Check the membership syntax

   The correct syntax for checking absence is value not in collection. The code misses in after not.

2. Step 2: Verify other parts

   List name and print statement are correct. The only error is missing in.

3. Final Answer:

   Missing in after not -> Option C

4. Quick Check:

   Use not in together [OK]

Hint: Always write not in together [OK]

Common Mistakes:

• Writing not items instead of not in items
• Forgetting in keyword
• Assuming not alone checks membership

5. You have a list words = ['cat', 'dog', 'bird']. You want to print all words that are NOT in the string text = 'I have a dog and a cat'. Which code correctly does this?

hard

A. for w in words:
if w not in text:
print(w)

B. for w in words:
if w in text:
print(w)

C. for w in words:
if not w text:
print(w)

D. for w in words:
if w not text:
print(w)

Solution

1. Step 1: Understand the goal

   We want to print words from the list that are NOT found inside the string text.

2. Step 2: Check each option's logic

   for w in words: if w not in text: print(w) uses if w not in text, which correctly checks absence. for w in words: if w in text: print(w) prints words that ARE in text, opposite of goal. for w in words: if not w text: print(w) has syntax error, missing in after w. for w in words: if w not text: print(w) has syntax error missing in.

3. Final Answer:

   for w in words: if w not in text: print(w) -> Option A

4. Quick Check:

   Use not in for absence check [OK]

Hint: Use if w not in text to find missing words [OK]

Common Mistakes:

• Omitting in keyword in various positions
• Forgetting in keyword
• Printing words that are present instead of absent