Why sets are used in Python - Performance Analysis

Time Complexity: Why sets are used

O(n)

Understanding Time Complexity

We want to understand why sets are chosen in Python programs.

Specifically, how using sets affects the speed of common tasks.

Scenario Under Consideration

Analyze the time complexity of this code snippet using a set.

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

if x in my_set:
    print("Found")
else:
    print("Not found")
    

This code adds numbers to a set and then checks if a number is inside it.

Identify Repeating Operations

Look at the loops and checks that repeat.

• Primary operation: Adding items to the set inside the loop.
• How many times: Exactly n times, once for each number.
• Secondary operation: Checking if x is in the set happens once.

How Execution Grows With Input

Adding each item takes about the same time, so total time grows as we add more items.

Input Size (n)	Approx. Operations
10	About 10 adds + 1 check
100	About 100 adds + 1 check
1000	About 1000 adds + 1 check

Pattern observation: The time to add grows directly with n, but checking if an item is in the set stays very fast no matter how big n is.

Final Time Complexity

Time Complexity: O(n)

This means adding n items takes time proportional to n, but checking membership is very fast and does not slow down as the set grows.

Common Mistake

[X] Wrong: "Checking if an item is in a set takes longer as the set gets bigger."

[OK] Correct: Sets use a special way to find items quickly, so checking membership usually takes the same short time no matter how many items are inside.

Interview Connect

Understanding why sets are fast for membership checks helps you write better code and explain your choices clearly in interviews.

Self-Check

"What if we used a list instead of a set? How would the time complexity for checking membership change?"

Practice

1. Which of the following is the main reason to use a set in Python?

easy

A. To store unique items without duplicates

B. To keep items in a specific order

C. To allow duplicate values

D. To store key-value pairs

Solution

1. Step 1: Understand the purpose of sets

   Sets automatically remove duplicate items, so they only keep unique elements.

2. Step 2: Compare with other data types

   Lists allow duplicates and keep order, dictionaries store key-value pairs, so they don't fit the main use of sets.

3. Final Answer:

   To store unique items without duplicates -> Option A

4. Quick Check:

   Sets = Unique items [OK]

Hint: Sets always keep unique items, no duplicates allowed [OK]

Common Mistakes:

• Thinking sets keep order
• Confusing sets with lists or dictionaries
• Assuming sets allow duplicates

2. Which of the following is the correct way to create a set in Python?

easy

A. my_set = {1, 2, 3}

B. my_set = [1, 2, 3]

C. my_set = (1, 2, 3)

D. my_set = {'a': 1, 'b': 2}

Solution

1. Step 1: Recall set syntax

   Sets are created using curly braces with comma-separated values, like {1, 2, 3}.

2. Step 2: Identify other data types

   Square brackets create lists, parentheses create tuples, and curly braces with key-value pairs create dictionaries.

3. Final Answer:

   my_set = {1, 2, 3} -> Option A

4. Quick Check:

   Curly braces with values = set [OK]

Hint: Use curly braces with values to create sets [OK]

Common Mistakes:

• Using square brackets instead of curly braces
• Confusing sets with dictionaries
• Using parentheses which create tuples

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

my_list = [1, 2, 2, 3, 4, 4, 4]
my_set = set(my_list)
print(my_set)

medium

A. {1, 2, 2, 3, 4, 4, 4}

B. [1, 2, 2, 3, 4, 4, 4]

C. {1, 2, 3, 4}

D. (1, 2, 3, 4)

Solution

1. Step 1: Convert list to set

   Using <code>set()</> on a list removes duplicates, so repeated numbers appear only once.

2. Step 2: Understand set output format

   Printing a set shows unique values inside curly braces without duplicates.

3. Final Answer:

   {1, 2, 3, 4} -> Option C

4. Quick Check:

   set(list with duplicates) = unique values [OK]

Hint: set() removes duplicates from any list or iterable [OK]

Common Mistakes:

• Expecting list output instead of set
• Thinking duplicates remain in set
• Confusing set with tuple or list syntax

4. Find the error in this code that tries to create a set with duplicate values:

my_set = {1, 2, 2, 3}
print(my_set)

medium

A. You must convert the set to a list before printing

B. Sets cannot have duplicate values, so this code will cause an error

C. The syntax for creating a set is wrong

D. The code is correct; duplicates are automatically removed

Solution

1. Step 1: Check set behavior with duplicates

   Sets automatically remove duplicates, so writing duplicates in the set literal is allowed but duplicates are ignored.

2. Step 2: Verify syntax and output

   The syntax is correct and printing the set will show unique values only.

3. Final Answer:

   The code is correct; duplicates are automatically removed -> Option D

4. Quick Check:

   Duplicates ignored in sets = code runs fine [OK]

Hint: Duplicates in set literals are ignored, no error occurs [OK]

Common Mistakes:

• Thinking duplicates cause errors in sets
• Believing set syntax is wrong with duplicates
• Trying to convert set to list unnecessarily

5. You have two lists:

list1 = [1, 2, 3, 4]
list2 = [3, 4, 5, 6]

How can you find the common elements between these lists efficiently using sets?

hard

A. Use list1 + list2 to combine and then remove duplicates

B. Use set(list1) & set(list2) to get the intersection

C. Use a for loop to check each element manually

D. Use set(list1) | set(list2) to get the union

Solution

1. Step 1: Convert lists to sets

   Convert both lists to sets to use set operations like intersection.

2. Step 2: Use intersection operator

   The & operator on sets returns elements common to both sets.

3. Final Answer:

   Use set(list1) & set(list2) to get the intersection -> Option B

4. Quick Check:

   Set intersection = common elements [OK]

Hint: Use & operator on sets to find common items fast [OK]

Common Mistakes:

• Using + operator which concatenates lists
• Using union instead of intersection
• Manually looping instead of using sets