Inverting a dictionary in Python - Time & Space Complexity

Time Complexity: Inverting a dictionary

O(n)

Understanding Time Complexity

When we invert a dictionary, we swap its keys and values. Analyzing time complexity helps us see how the work grows as the dictionary gets bigger.

We want to know: how does the time to invert change when the dictionary has more items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def invert_dict(d):
    inverted = {}
    for key, value in d.items():
        inverted[value] = key
    return inverted

This code creates a new dictionary where each original value becomes a key, and each original key becomes its value.

Identify Repeating Operations

• Primary operation: Looping through all key-value pairs in the dictionary.
• How many times: Once for each item in the dictionary.

How Execution Grows With Input

As the dictionary gets bigger, the number of steps grows directly with the number of items.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The work grows evenly as the dictionary size grows.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Inverting a dictionary takes the same time no matter how big it is."

[OK] Correct: The code must look at every item once, so more items mean more work.

Interview Connect

Understanding how loops affect time helps you explain your code clearly and shows you can think about efficiency, a key skill in programming.

Self-Check

"What if the dictionary values are not unique and we store lists of keys for each value? How would the time complexity change?"