Union and intersection in Python - Time & Space Complexity

Time Complexity: Union and intersection

O(n + m)

Understanding Time Complexity

When we find the union or intersection of two sets, we want to know how the time needed changes as the sets get bigger.

We ask: How does the work grow when the input sets grow?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def union_and_intersection(set1, set2):
    union = set1 | set2
    intersection = set1 & set2
    return union, intersection

This code finds the union and intersection of two sets using built-in operators.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Combining elements from both sets to form union and intersection.
• How many times: Each element in both sets is checked once during these operations.

How Execution Grows With Input

As the size of the sets grows, the time to find union and intersection grows roughly in proportion to the total number of elements.

Input Size (n)	Approx. Operations
10	About 20 checks
100	About 200 checks
1000	About 2000 checks

Pattern observation: Doubling the input roughly doubles the work needed.

Final Time Complexity

Time Complexity: O(n + m)

This means the time grows linearly with the size of both input sets combined.

Common Mistake

[X] Wrong: "Union and intersection take constant time because sets are fast."

[OK] Correct: Even though sets are fast, the operations still need to look at each element at least once, so time grows with input size.

Interview Connect

Understanding how set operations scale helps you explain your code clearly and shows you know how data size affects performance.

Self-Check

"What if we used lists instead of sets for union and intersection? How would the time complexity change?"