Adding and updating key-value pairs in Python - Time & Space Complexity

Time Complexity: Adding and updating key-value pairs

O(n)

Understanding Time Complexity

When we add or update key-value pairs in a dictionary, we want to know how the time it takes changes as the dictionary grows.

We ask: How does the work grow when the dictionary gets 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
my_dict[5] = 100

This code adds n key-value pairs to an empty dictionary, then updates the value for key 5.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding or updating a key-value pair in the dictionary inside the loop.
• How many times: The loop runs n times, so the add/update happens n times.

How Execution Grows With Input

Each time we add or update a key, the work is about the same, no matter how big the dictionary is.

Input Size (n)	Approx. Operations
10	About 10 adds/updates
100	About 100 adds/updates
1000	About 1000 adds/updates

Pattern observation: The total work grows directly with n, because each add/update takes roughly the same time.

Final Time Complexity

Time Complexity: O(n)

This means the time to add or update n items grows in a straight line with n.

Common Mistake

[X] Wrong: "Adding or updating a key takes longer as the dictionary gets bigger because it has to search through all keys."

[OK] Correct: Dictionaries use a special method that lets them find keys quickly without checking every item, so each add or update takes about the same time no matter the size.

Interview Connect

Understanding how adding and updating dictionary entries scales helps you explain how your code handles data efficiently, a skill useful in many programming tasks.

Self-Check

"What if we used a list of pairs instead of a dictionary? How would the time complexity change when adding or updating values?"