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

Practice

1. What does the union operation do when applied to two sets in Python?

easy

A. Combines all unique elements from both sets

B. Finds elements only in the first set

C. Finds elements only in the second set

D. Finds elements common to both sets

Solution

1. Step 1: Understand union operation

   The union of two sets includes every unique element from both sets without duplicates.

2. Step 2: Compare with other options

   Options B and C describe subsets, and D describes intersection, not union.

3. Final Answer:

   Combines all unique elements from both sets -> Option A

4. Quick Check:

   Union = all unique elements combined [OK]

Hint: Union joins all unique items from both sets [OK]

Common Mistakes:

• Confusing union with intersection
• Thinking union only takes elements from one set
• Assuming union keeps duplicates

2. Which of the following is the correct syntax to find the intersection of two sets a and b in Python?

easy

A. a + b

B. a | b

C. a & b

D. a - b

Solution

1. Step 1: Recall intersection syntax

   In Python, the intersection of two sets is found using the & operator or the .intersection() method.

2. Step 2: Check other operators

   | is union, + is invalid for sets, - is difference.

3. Final Answer:

   a & b -> Option C

4. Quick Check:

   Intersection uses & operator [OK]

Hint: Use & for intersection of sets [OK]

Common Mistakes:

• Using | instead of & for intersection
• Trying to add sets with + operator
• Confusing difference (-) with intersection

3. What is the output of the following code?

set1 = {1, 2, 3, 4}
set2 = {3, 4, 5, 6}
print(set1.intersection(set2))

medium

A. {1, 2}

B. {5, 6}

C. {1, 2, 3, 4, 5, 6}

D. {3, 4}

Solution

1. Step 1: Identify intersection elements

   The intersection contains elements present in both sets: {3, 4}.

2. Step 2: Confirm output

   Printing the intersection returns {3, 4} exactly.

3. Final Answer:

   {3, 4} -> Option D

4. Quick Check:

   Common elements = {3, 4} [OK]

Hint: Intersection shows only common elements [OK]

Common Mistakes:

• Confusing union with intersection output
• Expecting all elements combined
• Mixing up set contents

4. The following code is intended to print the union of two sets, but it causes an error. What is the problem?

set1 = {1, 2, 3}
set2 = {3, 4, 5}
print(set1 + set2)

medium

A. Sets cannot be added with + operator

B. The sets are empty

C. The print statement is missing parentheses

D. The sets have overlapping elements

Solution

1. Step 1: Identify the error cause

   Python sets do not support the + operator; this causes a TypeError.

2. Step 2: Correct way to union sets

   Use | operator or .union() method to combine sets.

3. Final Answer:

   Sets cannot be added with + operator -> Option A

4. Quick Check:

   + operator invalid for sets [OK]

Hint: Use | or .union(), not + for sets [OK]

Common Mistakes:

• Trying to add sets with +
• Ignoring error message
• Confusing list addition with set union

5. Given two lists of student names, list1 = ['Anna', 'Bob', 'Cara'] and list2 = ['Bob', 'Diana', 'Anna'], which Python code correctly finds students present in both lists using set operations?

hard

A. list1 | list2

B. set(list1) & set(list2)

C. set(list1) + set(list2)

D. list1.intersection(list2)

Solution

1. Step 1: Convert lists to sets for set operations

   Lists must be converted to sets to use intersection (&) operator.

2. Step 2: Use & operator to find common elements

   set(list1) & set(list2) returns elements in both sets.

3. Step 3: Check other options

   list1 | list2 uses | on lists (invalid), C uses + on sets (invalid), D calls intersection on list (no such method).

4. Final Answer:

   set(list1) & set(list2) -> Option B

5. Quick Check:

   Convert lists to sets, then & for intersection [OK]

Hint: Convert lists to sets before intersection [OK]

Common Mistakes:

• Using + or | on lists directly
• Calling set methods on lists
• Not converting lists to sets first