Set membership testing in Python - Time & Space Complexity

Time Complexity: Set membership testing

O(1)

Understanding Time Complexity

Checking if an item is in a set is a common task in programming.

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

my_set = {1, 2, 3, 4, 5}
item = 3
if item in my_set:
    print("Found")
else:
    print("Not found")

This code checks if a number is inside a set and prints a message.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking if the item is in the set.
• How many times: This check happens once per query.

How Execution Grows With Input

Checking membership in a set stays very fast even if the set grows.

Input Size (n)	Approx. Operations
10	About 1 operation
100	About 1 operation
1000	About 1 operation

Pattern observation: The time to check does not grow much as the set gets bigger.

Final Time Complexity

Time Complexity: O(1)

This means the check takes about the same time no matter how big the set is.

Common Mistake

[X] Wrong: "Checking if an item is in a set takes longer as the set grows."

[OK] Correct: Sets use a special way to find items quickly, so the time stays almost the same even if the set is large.

Interview Connect

Understanding how fast set membership works helps you write efficient code and answer questions about data lookup speed.

Self-Check

"What if we used a list instead of a set? How would the time complexity change?"

Practice

1.

Which operator is used to check if an element exists inside a set in Python?

easy

A. contains

B. has

C. exists

D. in

Solution

1. Step 1: Understand set membership

   In Python, the in keyword checks if an element is present in a set.

2. Step 2: Identify correct operator

   Other options like has, exists, and contains are not valid Python operators for membership testing.

3. Final Answer:

   in -> Option D

4. Quick Check:

   Use in to test membership [OK]

Hint: Remember: use 'in' to check if item is inside a set [OK]

Common Mistakes:

• Using 'has' instead of 'in'
• Trying 'exists' keyword
• Using 'contains' which is not a Python operator

2.

Which of the following is the correct syntax to check if 5 is NOT in the set {1, 2, 3, 4}?

easy

A. 5 not in {1, 2, 3, 4}

B. not 5 in {1, 2, 3, 4}

C. 5 !in {1, 2, 3, 4}

D. 5 notinside {1, 2, 3, 4}

Solution

1. Step 1: Recall correct syntax for 'not in'

   The correct syntax to check if an element is not in a set is: element not in set.

2. Step 2: Evaluate each option

   5 not in {1, 2, 3, 4} uses correct syntax. not 5 in {1, 2, 3, 4} is incorrect because 'not' must come after the element. 5 !in {1, 2, 3, 4} uses invalid operator '!in'. 5 notinside {1, 2, 3, 4} uses a non-existent keyword 'notinside'.

3. Final Answer:

   5 not in {1, 2, 3, 4} -> Option A

4. Quick Check:

   Use 'not in' with element first [OK]

Hint: Write 'element not in set' to check absence [OK]

Common Mistakes:

• Using '!in' instead of 'not in'
• Placing 'not' before element
• Using invalid keywords like 'notinside'

3.

What will be the output of the following code?

my_set = {10, 20, 30}
print(25 in my_set)

medium

A. True

B. False

C. 25

D. Error

Solution

1. Step 1: Understand the set contents

   The set my_set contains 10, 20, and 30. It does not contain 25.

2. Step 2: Evaluate membership test

   The expression 25 in my_set checks if 25 is in the set. Since it is not, the result is False.

3. Final Answer:

   False -> Option B

4. Quick Check:

   25 not in set means False [OK]

Hint: If element missing in set, 'in' returns False [OK]

Common Mistakes:

• Assuming output is the element itself
• Confusing True/False for membership
• Expecting an error for missing element

4.

Find the error in this code snippet:

my_set = {1, 2, 3}
if 4 notin my_set:
    print("4 is not in the set")

medium

A. The keyword 'notin' is invalid

B. The set declaration is wrong

C. Missing colon after if statement

D. Print statement syntax error

Solution

1. Step 1: Check syntax of membership test

   The correct keyword to check absence is not in with a space, not notin.

2. Step 2: Verify other parts of code

   The set declaration is correct, colon after if is present, and print syntax is valid.

3. Final Answer:

   The keyword 'notin' is invalid -> Option A

4. Quick Check:

   Use 'not in' with space, not 'notin' [OK]

Hint: Remember: 'not in' has a space between words [OK]

Common Mistakes:

• Writing 'notin' as one word
• Forgetting colon after if
• Misreading print syntax

5.

Given the list nums = [1, 2, 2, 3, 4, 4, 5], which code snippet correctly prints Found only if 3 is in the unique set of numbers?

A) if 3 in nums:
       print("Found")

B) if 3 in set(nums):
       print("Found")

C) if 3 not in set(nums):
       print("Found")

D) if 3 not in nums:
       print("Found")

hard

A. if 3 in nums:
print("Found")

B. if 3 not in nums:
print("Found")

C. if 3 in set(nums):
print("Found")

D. if 3 not in set(nums):
print("Found")

Solution

1. Step 1: Understand the requirement

   We want to check if 3 is in the unique set of numbers from the list, so duplicates are ignored.

2. Step 2: Analyze each option

   if 3 in nums: print("Found") checks 3 in the list (with duplicates). if 3 in set(nums): print("Found") converts list to set and checks membership correctly. if 3 not in set(nums): print("Found") prints 'Found' if 3 is NOT in the set, which is wrong. if 3 not in nums: print("Found") checks 3 not in list, also wrong.

3. Final Answer:

   if 3 in set(nums): print("Found") -> Option C

4. Quick Check:

   Convert list to set before membership test [OK]

Hint: Convert list to set before membership test for uniqueness [OK]

Common Mistakes:

• Checking membership directly in list with duplicates
• Using 'not in' instead of 'in'
• Confusing list and set membership