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