Subset and superset checks in Python - Time & Space Complexity

Time Complexity: Subset and superset checks

O(n)

Understanding Time Complexity

When we check if one set is inside another or if one set contains another, we want to know how long this takes as the sets grow.

We ask: How does the time to check subset or superset grow with the size of the sets?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

set_a = {1, 2, 3, 4, 5}
set_b = {2, 3}

# Check if set_b is a subset of set_a
result = set_b.issubset(set_a)

# Check if set_a is a superset of set_b
result2 = set_a.issuperset(set_b)

This code checks if one set is fully contained in another using built-in subset and superset methods.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each element of the smaller set against the larger set.
• How many times: Once for each element in the smaller set.

How Execution Grows With Input

As the smaller set grows, the number of checks grows roughly the same amount.

Input Size (n)	Approx. Operations
10	About 10 membership checks
100	About 100 membership checks
1000	About 1000 membership checks

Pattern observation: The time grows in a straight line with the size of the smaller set.

Final Time Complexity

Time Complexity: O(n)

This means the time to check grows directly with the number of elements in the smaller set.

Common Mistake

[X] Wrong: "Checking subset or superset takes time based on the size of both sets multiplied together."

[OK] Correct: The check only needs to look at each element in the smaller set once, because checking membership in a set is very fast (average O(1) time).

Interview Connect

Understanding how subset and superset checks scale helps you reason about set operations in real code, showing you can think about efficiency clearly.

Self-Check

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

Practice

1. Which of the following statements correctly describes a subset in Python sets?

easy

A. All elements of set A are in set B.

B. Set A has more elements than set B.

C. Set A and set B have no common elements.

D. Set A and set B have exactly the same elements.

Solution

1. Step 1: Understand subset definition

   A set A is a subset of set B if every element in A is also in B.

2. Step 2: Match definition to options

   All elements of set A are in set B. states all elements of A are in B, which matches the subset definition.

3. Final Answer:

   All elements of set A are in set B. -> Option A

4. Quick Check:

   Subset means all elements inside another set [OK]

Hint: Subset means every item of one set is inside another [OK]

Common Mistakes:

• Confusing subset with superset
• Thinking subsets must have fewer elements
• Assuming no common elements means subset

2. Which of the following is the correct syntax to check if set A is a superset of set B in Python?

easy

A. A.issubset(B)

B. A <= B

C. A.issuperset(B)

D. A < B

Solution

1. Step 1: Recall superset method

   To check if A is a superset of B, use A.issuperset(B) or A >= B.

2. Step 2: Identify correct option

   A.issuperset(B) uses A.issuperset(B), which is the correct method.

3. Final Answer:

   A.issuperset(B) -> Option C

4. Quick Check:

   Superset check uses issuperset() method [OK]

Hint: Use issuperset() to check if A contains all of B [OK]

Common Mistakes:

• Using issubset() instead of issuperset()
• Using <= or < for superset checks
• Confusing method names

3. What will be the output of the following code?

set_a = {1, 2, 3}
set_b = {1, 2, 3, 4, 5}
print(set_a <= set_b)
print(set_b >= set_a)

medium

A. False\nFalse

B. False\nTrue

C. True\nFalse

D. True\nTrue

Solution

1. Step 1: Evaluate set_a <= set_b

   set_a has elements {1,2,3}, all of which are in set_b, so set_a is subset of set_b, result is True.

2. Step 2: Evaluate set_b >= set_a

   set_b contains all elements of set_a, so set_b is superset of set_a, result is True.

3. Final Answer:

   True True -> Option D

4. Quick Check:

   Subset and superset checks both True [OK]

Hint: <= and >= check subset and superset respectively [OK]

Common Mistakes:

• Mixing up <= and >= operators
• Assuming strict subset/superset without equality
• Forgetting sets can be equal

4. The following code is intended to check if set A is a subset of set B, but it raises an error. What is the problem?

set_a = {1, 2}
set_b = {1, 2, 3}
result = set_a.subset(set_b)
print(result)

medium

A. Sets cannot be compared using methods.

B. The method name should be issubset(), not subset().

C. The sets must be converted to lists first.

D. The print statement is missing parentheses.

Solution

1. Step 1: Identify method name error

   The correct method to check subset is issubset(), not subset().

2. Step 2: Confirm correct usage

   Using set_a.issubset(set_b) returns True or False without error.

3. Final Answer:

   The method name should be issubset(), not subset(). -> Option B

4. Quick Check:

   issubset() is correct method name [OK]

Hint: Use issubset(), not subset(), to check subsets [OK]

Common Mistakes:

• Using wrong method names
• Thinking sets need conversion to lists
• Confusing print syntax errors

5. Given two sets:

set_x = {2, 4, 6, 8}
set_y = {4, 6}

Which of the following expressions will return True for checking if set_y is a proper subset of set_x (subset but not equal)?

hard

A. set_y < set_x

B. set_y >= set_x

C. set_x.issubset(set_y)

D. set_y.issuperset(set_x)

Solution

1. Step 1: Understand proper subset

   A proper subset means all elements of set_y are in set_x, and sets are not equal.

2. Step 2: Analyze options

   set_y < set_x uses < operator which checks proper subset (subset but not equal). set_y >= set_x checks superset (wrong direction). set_x.issubset(set_y) reverses the sets (wrong). set_y.issuperset(set_x) is wrong (issuperset).

3. Final Answer:

   set_y < set_x -> Option A

4. Quick Check:

   Proper subset uses < operator [OK]

Hint: Use < for proper subset (subset but not equal) [OK]

Common Mistakes:

• Using >= which checks superset
• Reversing the subset direction
• Confusing issubset() with issuperset()