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