Set algebra (union, intersection, difference) in Swift - Time & Space Complexity

Time Complexity: Set algebra (union, intersection, difference)

O(n)

Understanding Time Complexity

When working with sets, it's important to know how the time to combine or compare them grows as the sets get bigger.

We want to understand how fast operations like union, intersection, and difference run as the number of items increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

let setA: Set = [1, 2, 3, 4, 5]
let setB: Set = [4, 5, 6, 7, 8]

let unionSet = setA.union(setB)
let intersectionSet = setA.intersection(setB)
let differenceSet = setA.subtracting(setB)
    

This code creates two sets and performs union, intersection, and difference operations on them.

Identify Repeating Operations

• Primary operation: Checking each element of one set against the other set.
• How many times: Each element in the first set is checked once during these operations.

How Execution Grows With Input

As the sets get bigger, the number of checks grows roughly in direct proportion to the size of the sets.

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

Pattern observation: The work grows steadily as the number of elements grows, not faster or slower.

Final Time Complexity

Time Complexity: O(n)

This means the time to do these set operations grows in a straight line with the number of elements.

Common Mistake

[X] Wrong: "Set operations take a long time because they compare every element to every other element."

[OK] Correct: Sets use fast lookups, so each element is checked quickly without comparing to all others.

Interview Connect

Understanding how set operations scale helps you explain efficient data handling in real projects and shows you know how to reason about performance.

Self-Check

"What if we changed the sets to arrays instead? How would the time complexity change?"