Set operations (Union, Intersect, Except) in C Sharp (C#) - Time & Space Complexity

Time Complexity: Set operations (Union, Intersect, Except)

O(n + m)

Understanding Time Complexity

When we use set operations like Union, Intersect, and Except, we want to know how long these actions take as the sets get bigger.

We ask: How does the time needed grow when the number of items in the sets grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

var setA = new HashSet<int>() {1, 2, 3, 4, 5};
var setB = new HashSet<int>() {4, 5, 6, 7, 8};

var union = setA.Union(setB).ToHashSet();
var intersect = setA.Intersect(setB).ToHashSet();
var except = setA.Except(setB).ToHashSet();
    

This code creates two sets and finds their union, intersection, and difference.

Identify Repeating Operations

Look at what repeats when doing these set operations.

• Primary operation: Checking each item in one set against the other set.
• How many times: Each item in the first set is checked once, and sometimes items in the second set are also checked.

How Execution Grows With Input

As the sets get bigger, the number of checks grows roughly in a straight line with the total number of items.

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

Pattern observation: Doubling the size of the sets roughly doubles the work done.

Final Time Complexity

Time Complexity: O(n + m)

This means the time grows linearly with the total number of items in both sets.

Common Mistake

[X] Wrong: "Set operations always take the same time no matter how big the sets are."

[OK] Correct: Actually, the time depends on how many items are in the sets because each item needs to be checked.

Interview Connect

Understanding how set operations scale helps you explain your code clearly and shows you know how to handle data efficiently.

Self-Check

"What if we used lists instead of sets for these operations? How would the time complexity change?"