HashSet for unique elements in C Sharp (C#) - Time & Space Complexity

Time Complexity: HashSet for unique elements

O(n)

Understanding Time Complexity

We want to understand how fast a HashSet can add and check unique items.

How does the time to add or check items grow as we add more elements?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

HashSet<int> uniqueNumbers = new HashSet<int>();
int[] numbers = {1, 2, 3, 2, 4, 5, 3};

foreach (int num in numbers)
{
    uniqueNumbers.Add(num);
}
    

This code adds numbers to a HashSet to keep only unique values.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding each number to the HashSet.
• How many times: Once for each number in the input array.

How Execution Grows With Input

Each new number is checked and added quickly, so the time grows roughly in a straight line with the number of items.

Input Size (n)	Approx. Operations
10	About 10 add/check operations
100	About 100 add/check operations
1000	About 1000 add/check operations

Pattern observation: The work grows evenly as the input grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to add all items grows directly with the number of items.

Common Mistake

[X] Wrong: "Adding to a HashSet takes longer and longer as it gets bigger."

[OK] Correct: HashSet uses a smart way to find spots quickly, so adding stays fast even with many items.

Interview Connect

Knowing how HashSet works helps you explain why it's great for finding unique items quickly in real projects.

Self-Check

"What if we used a List instead of a HashSet to keep unique items? How would the time complexity change?"