Dictionary use cases in Python - Time & Space Complexity

Time Complexity: Dictionary use cases

O(n)

Understanding Time Complexity

When using dictionaries in Python, it is important to understand how fast operations like adding, looking up, or removing items happen.

We want to know how the time to do these actions changes as the dictionary grows bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

my_dict = {}
for i in range(n):
    my_dict[i] = i * 2

value = my_dict.get(5)

if 10 in my_dict:
    del my_dict[10]

This code adds n items to a dictionary, then looks up a value, and finally deletes an item if it exists.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding items to the dictionary inside the loop.
• How many times: The loop runs n times, adding one item each time.
• Lookup and deletion happen once each, outside the loop.

How Execution Grows With Input

As n grows, adding items takes more steps because we do it n times.

Input Size (n)	Approx. Operations
10	About 10 additions + 2 single operations
100	About 100 additions + 2 single operations
1000	About 1000 additions + 2 single operations

Pattern observation: The total work grows roughly in direct proportion to n because each addition takes about the same time.

Final Time Complexity

Time Complexity: O(n)

This means the time to add n items grows linearly with n, while lookups and deletions take about the same short time no matter the size.

Common Mistake

[X] Wrong: "Looking up or deleting an item in a dictionary takes longer as the dictionary gets bigger."

[OK] Correct: Dictionaries use a special method that lets them find or remove items quickly, almost instantly, no matter how many items they hold.

Interview Connect

Understanding how dictionary operations scale helps you write fast and efficient code, a skill that shows you know how to handle data well in real projects.

Self-Check

"What if we used a list instead of a dictionary for storing items? How would the time complexity for lookup change?"

Practice

1. What is the main purpose of a dictionary in Python?

easy

A. To store data as key-value pairs for quick access

B. To store data in a fixed order like a list

C. To perform mathematical calculations

D. To create a sequence of numbers

Solution

1. Step 1: Understand dictionary structure

   Dictionaries store data in pairs where each key maps to a value.

2. Step 2: Identify dictionary use case

   This structure allows fast lookup by key, unlike lists which use indexes.

3. Final Answer:

   To store data as key-value pairs for quick access -> Option A

4. Quick Check:

   Dictionaries = key-value pairs [OK]

Hint: Remember: dictionaries use keys to find values fast [OK]

Common Mistakes:

• Confusing dictionaries with lists or sets
• Thinking dictionaries keep order like lists
• Assuming dictionaries store only numbers

2. Which of the following is the correct way to add a new key-value pair to a dictionary my_dict?

easy

A. my_dict.append('key', 'value')

B. my_dict.add('key', 'value')

C. my_dict['key'] = 'value'

D. my_dict.insert('key', 'value')

Solution

1. Step 1: Recall dictionary syntax for adding items

   To add or update a key-value pair, use square brackets with the key and assign a value.

2. Step 2: Check each option

   Only my_dict['key'] = 'value' correctly adds or updates the dictionary.

3. Final Answer:

   my_dict['key'] = 'value' -> Option C

4. Quick Check:

   Use square brackets to add/update dict items [OK]

Hint: Use square brackets and assignment to add dict items [OK]

Common Mistakes:

• Using list methods like append or insert on dictionaries
• Trying to use a non-existent add() method
• Confusing dictionary syntax with list syntax

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

my_dict = {'a': 1, 'b': 2}
my_dict['c'] = 3
print(my_dict)

medium

A. Error: Cannot add new key

B. {'a': 1, 'b': 2}

C. {'c': 3}

D. {'a': 1, 'b': 2, 'c': 3}

Solution

1. Step 1: Understand dictionary update

   Adding my_dict['c'] = 3 adds a new key 'c' with value 3.

2. Step 2: Print the updated dictionary

   Printing shows all keys and values including the new one.

3. Final Answer:

   {'a': 1, 'b': 2, 'c': 3} -> Option D

4. Quick Check:

   Adding key updates dict content [OK]

Hint: Adding key-value pairs updates dictionary instantly [OK]

Common Mistakes:

• Expecting original dict without new key
• Thinking print shows only last added key
• Assuming error when adding new keys

4. Find the error in this code snippet:

my_dict = {'x': 10, 'y': 20}
print(my_dict['z'])

medium

A. KeyError because 'z' is not in the dictionary

B. SyntaxError due to wrong brackets

C. TypeError because dictionary keys must be integers

D. No error, prints 0

Solution

1. Step 1: Check dictionary keys

   Keys are 'x' and 'y', but 'z' is not present.

2. Step 2: Accessing missing key causes error

   Trying to print my_dict['z'] raises a KeyError.

3. Final Answer:

   KeyError because 'z' is not in the dictionary -> Option A

4. Quick Check:

   Access missing key = KeyError [OK]

Hint: Accessing missing keys causes KeyError [OK]

Common Mistakes:

• Assuming missing keys return 0 or None
• Confusing KeyError with SyntaxError
• Trying to use wrong bracket types

5. Given a list of tuples representing student names and scores:

students = [('Alice', 85), ('Bob', 90), ('Alice', 95)]

Which code correctly creates a dictionary with the latest score for each student?

hard

A. scores = dict(students)
scores['Alice'] = 85

B. scores = {name: score for name, score in students}

C. scores = {}
for name, score in students:
if name not in scores:
scores[name] = score

D. scores = {name: max(score) for name, score in students}

Solution

1. Step 1: Understand dictionary comprehension behavior

   When keys repeat, the last value overwrites earlier ones.

2. Step 2: Check each option

   scores = {name: score for name, score in students} uses comprehension that keeps the last score for 'Alice' (95). scores = dict(students) scores['Alice'] = 85 wrongly resets 'Alice' score. scores = {} for name, score in students: if name not in scores: scores[name] = score keeps only first score. scores = {name: max(score) for name, score in students} is invalid syntax.

3. Final Answer:

   scores = {name: score for name, score in students} -> Option B

4. Quick Check:

   Dict comprehension overwrites duplicate keys [OK]

Hint: Dict comprehension keeps last value for duplicate keys [OK]

Common Mistakes:

• Assuming dict keeps first value for duplicates
• Using invalid syntax for max(score)
• Manually overwriting values incorrectly