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

Practice

1. Which method is used to add a new element to a Python set?

easy

A. add()

B. append()

C. insert()

D. push()

Solution

1. Step 1: Understand set methods

   Sets in Python use add() to add elements, unlike lists which use append().

2. Step 2: Identify correct method for sets

   insert() and push() are not valid set methods.

3. Final Answer:

   add() -> Option A

4. Quick Check:

   Use add() to add elements to sets [OK]

Hint: Remember: sets use add(), lists use append() [OK]

Common Mistakes:

• Confusing list methods with set methods
• Trying to use append() on sets
• Using insert() which is for lists

2. Which of the following is the correct syntax to remove an element 5 from a set s without causing an error if 5 is not present?

easy

A. s.remove(5)

B. s.delete(5)

C. s.pop(5)

D. s.discard(5)

Solution

1. Step 1: Understand remove() vs discard()

   remove() raises an error if the element is missing, but discard() does not.

2. Step 2: Check method validity

   delete() is not a set method, and pop() removes an arbitrary element without arguments.

3. Final Answer:

   s.discard(5) -> Option D

4. Quick Check:

   Use discard() to safely remove elements [OK]

Hint: Use discard() to avoid errors when removing [OK]

Common Mistakes:

• Using remove() without checking element presence
• Trying to use delete() which doesn't exist
• Passing arguments to pop() which takes none

3. What will be the output of the following code?

fruits = {'apple', 'banana', 'cherry'}
fruits.add('orange')
fruits.remove('banana')
print(fruits)

medium

A. {'apple', 'cherry', 'orange'}

B. {'apple', 'banana', 'cherry', 'orange'}

C. {'apple', 'banana', 'orange'}

D. Error

Solution

1. Step 1: Add 'orange' to the set

   Using add('orange') adds 'orange' to the set, so now it has {'apple', 'banana', 'cherry', 'orange'}.

2. Step 2: Remove 'banana' from the set

   remove('banana') deletes 'banana', leaving {'apple', 'cherry', 'orange'}.

3. Final Answer:

   {'apple', 'cherry', 'orange'} -> Option A

4. Quick Check:

   add() adds, remove() deletes existing element [OK]

Hint: Add then remove changes set contents accordingly [OK]

Common Mistakes:

• Expecting banana to remain after remove()
• Thinking add() replaces elements
• Confusing set order in output

4. The following code throws an error. What is the cause and how to fix it?

numbers = {1, 2, 3}
numbers.remove(4)
print(numbers)

medium

A. SyntaxError due to wrong method; fix by using delete(4)

B. No error; output is {1, 2, 3}

C. KeyError because 4 is not in set; fix by using discard(4)

D. TypeError because remove() needs a list; fix by converting set to list

Solution

1. Step 1: Identify error cause

   remove(4) raises a KeyError because 4 is not in the set.

2. Step 2: Fix error using discard()

   Replacing remove(4) with discard(4) avoids error even if 4 is missing.

3. Final Answer:

   KeyError because 4 is not in set; fix by using discard(4) -> Option C

4. Quick Check:

   remove() errors if missing; discard() does not [OK]

Hint: Use discard() to avoid errors when unsure element exists [OK]

Common Mistakes:

• Assuming remove() never errors
• Trying to use delete() which is invalid
• Confusing error types

5. Given a set nums = {1, 2, 3, 4, 5}, which code snippet correctly adds 6 and removes 2 safely without errors, even if 2 might not be present?

hard

A. nums.add(6)
nums.remove(2)

B. nums.add(6)
nums.discard(2)

C. nums.append(6)
nums.discard(2)

D. nums.add(6)
nums.delete(2)

Solution

1. Step 1: Add element 6 correctly

   add(6) is the correct method to add an element to a set.

2. Step 2: Remove element 2 safely

   discard(2) removes 2 without error if missing; remove(2) could cause error.

3. Final Answer:

   nums.add(6) nums.discard(2) -> Option B

4. Quick Check:

   add() to add, discard() to safely remove [OK]

Hint: Add with add(), remove safely with discard() [OK]

Common Mistakes:

• Using append() which is for lists
• Using remove() without checking element presence
• Trying to use delete() which doesn't exist