Nested dictionaries in Python - Time & Space Complexity

Time Complexity: Nested dictionaries

O(n * m)

Understanding Time Complexity

When working with nested dictionaries, it's important to know how the time to access or process data grows as the dictionary gets bigger.

We want to find out how the number of steps changes when we loop through nested dictionaries.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

data = {
    'a': {'x': 1, 'y': 2},
    'b': {'x': 3, 'y': 4},
    'c': {'x': 5, 'y': 6}
}

for outer_key in data:
    for inner_key in data[outer_key]:
        print(data[outer_key][inner_key])

This code loops through a dictionary where each value is another dictionary, printing all inner values.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops over outer and inner dictionaries.
• How many times: Outer loop runs once per outer key; inner loop runs once per inner key for each outer key.

How Execution Grows With Input

As the number of outer keys and inner keys grows, the total steps grow by multiplying these counts.

Input Size (outer keys x inner keys)	Approx. Operations
10 x 5 = 50	About 50 steps
100 x 5 = 500	About 500 steps
1000 x 5 = 5000	About 5000 steps

Pattern observation: The total work grows by multiplying the number of outer keys by the number of inner keys.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows proportionally to the number of outer keys times the number of inner keys.

Common Mistake

[X] Wrong: "The time grows only with the number of outer keys because the inner dictionaries are small."

[OK] Correct: Even if inner dictionaries are small, the total time depends on both outer and inner sizes multiplied together, so ignoring inner keys underestimates the time.

Interview Connect

Understanding how nested loops over dictionaries affect time helps you explain your code clearly and reason about performance in real projects.

Self-Check

"What if the inner dictionaries had different sizes? How would that affect the time complexity?"