Adding and removing set elements in Python - Time & Space Complexity

Time Complexity: Adding and removing set elements

O(n)

Understanding Time Complexity

When we add or remove items from a set, we want to know how the time it takes changes as the set grows.

We ask: How does the work grow when the set gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

my_set = set()

for i in range(n):
    my_set.add(i)

for i in range(n):
    my_set.remove(i)

This code adds numbers from 0 to n-1 into a set, then removes them one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding and removing elements from the set.
• How many times: Each operation happens n times, once per loop iteration.

How Execution Grows With Input

Each add or remove takes about the same time no matter the set size, so total work grows steadily with n.

Input Size (n)	Approx. Operations
10	About 20 operations (10 adds + 10 removes)
100	About 200 operations (100 adds + 100 removes)
1000	About 2000 operations (1000 adds + 1000 removes)

Pattern observation: The total work grows in a straight line as n grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to add and remove all elements grows directly with the number of elements.

Common Mistake

[X] Wrong: "Adding or removing from a set takes longer as the set gets bigger because it has to search through all elements."

[OK] Correct: Sets use a special way to find elements quickly, so each add or remove takes about the same time no matter the set size.

Interview Connect

Understanding how set operations scale helps you explain why sets are great for fast lookups and changes, a useful skill in many coding problems.

Self-Check

"What if we used a list instead of a set for adding and removing elements? How would the time complexity change?"