Dictionary iteration in Python - Time & Space Complexity

Time Complexity: Dictionary iteration

O(n)

Understanding Time Complexity

When we loop through a dictionary, we want to know how the time it takes changes as the dictionary gets bigger.

We ask: How does the work grow when we look at every item in the dictionary?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

my_dict = {"a": 1, "b": 2, "c": 3}
for key, value in my_dict.items():
    print(f"Key: {key}, Value: {value}")

This code goes through each key and value in the dictionary and prints them.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping over each key-value pair in the dictionary.
• How many times: Once for every item in the dictionary.

How Execution Grows With Input

As the dictionary gets bigger, the number of times we print grows the same way.

Input Size (n)	Approx. Operations
10	10 prints
100	100 prints
1000	1000 prints

Pattern observation: The work grows directly with the number of items.

Final Time Complexity

Time Complexity: O(n)

This means if the dictionary doubles in size, the time to loop through it also doubles.

Common Mistake

[X] Wrong: "Looping over a dictionary is always constant time because dictionaries are fast."

[OK] Correct: While looking up one item is fast, going through every item takes time proportional to how many items there are.

Interview Connect

Understanding how looping through dictionaries grows with size helps you explain your code clearly and shows you know how to think about efficiency.

Self-Check

"What if we only looped through the keys and not the values? How would the time complexity change?"