Removing dictionary entries in Python - Time & Space Complexity

Time Complexity: Removing dictionary entries

O(n)

Understanding Time Complexity

When we remove entries from a dictionary, we want to know how the time it takes changes as the dictionary grows.

We ask: How does removing items scale with the number of entries?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

my_dict = {i: i*2 for i in range(n)}
for key in list(my_dict.keys()):
    if key % 2 == 0:
        del my_dict[key]

This code creates a dictionary with n entries and removes all entries with even keys.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping over all keys in the dictionary.
• How many times: Exactly n times, once for each key.
• Secondary operation: Deleting entries from the dictionary inside the loop.

How Execution Grows With Input

As the dictionary size grows, the number of operations grows roughly the same way.

Input Size (n)	Approx. Operations
10	About 10 checks and some deletions
100	About 100 checks and deletions
1000	About 1000 checks and deletions

Pattern observation: The work grows directly with the number of entries; doubling entries roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to remove entries grows in a straight line with the number of items in the dictionary.

Common Mistake

[X] Wrong: "Deleting items from a dictionary inside a loop is constant time and does not affect overall time."

[OK] Correct: Each deletion takes average constant time, and since deletions happen inside a loop over n items, the total time grows with n.

Interview Connect

Understanding how dictionary operations scale helps you write efficient code and explain your choices clearly in interviews.

Self-Check

"What if we removed items without converting keys to a list first? How would the time complexity change?"