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?"

Practice

1. What is a nested dictionary in Python?
Example: {'person': {'name': 'Alice', 'age': 30}}

easy

A. A dictionary with only one key

B. A dictionary inside another dictionary

C. A list inside a dictionary

D. A dictionary with numeric keys only

Solution

1. Step 1: Understand dictionary structure

   A dictionary stores key-value pairs. Nested means one value is itself a dictionary.

2. Step 2: Analyze the example

   In {'person': {'name': 'Alice', 'age': 30}}, the value for 'person' is another dictionary.

3. Final Answer:

   A dictionary inside another dictionary -> Option B

4. Quick Check:

   Nested dictionary = dictionary inside dictionary [OK]

Hint: Look for a dictionary as a value inside another dictionary [OK]

Common Mistakes:

• Confusing nested dictionary with list inside dictionary
• Thinking nested means only one key
• Assuming keys must be numbers

2. Which of the following is the correct way to access the value 'blue' in this nested dictionary?

colors = {'shirt': {'color': 'blue', 'size': 'M'}}

easy

A. colors['shirt']['size']

B. colors['color']['shirt']

C. colors['shirt']['color']

D. colors['color']

Solution

1. Step 1: Identify keys to reach 'blue'

   'blue' is the value of 'color' inside the dictionary for key 'shirt'.

2. Step 2: Use correct key order

   Access outer key 'shirt' first, then inner key 'color': colors['shirt']['color'].

3. Final Answer:

   colors['shirt']['color'] -> Option C

4. Quick Check:

   Outer then inner keys = colors['shirt']['color'] [OK]

Hint: Use outer key first, then inner key in square brackets [OK]

Common Mistakes:

• Swapping the order of keys
• Trying to access keys that don't exist
• Using only one key for nested value

3. What will be the output of this code?

data = {'user': {'name': 'Bob', 'age': 25}}
print(data['user']['age'])

medium

A. 25

B. Bob

C. {'name': 'Bob', 'age': 25}

D. KeyError

Solution

1. Step 1: Access nested dictionary value

   data['user'] gives {'name': 'Bob', 'age': 25}.

2. Step 2: Access 'age' key inside nested dictionary

   data['user']['age'] gives 25.

3. Final Answer:

   25 -> Option A

4. Quick Check:

   Nested key access returns 25 [OK]

Hint: Access keys step-by-step to get nested value [OK]

Common Mistakes:

• Printing the whole nested dictionary instead of value
• Using wrong key order
• Expecting string 'Bob' instead of age

4. Find the error in this code snippet:

info = {'book': {'title': 'Python 101', 'pages': 200}}
print(info['book']['author'])

medium

A. No error, prints None

B. SyntaxError due to missing colon

C. TypeError because 'book' is not a dictionary

D. KeyError because 'author' key does not exist

Solution

1. Step 1: Check keys in nested dictionary

   info['book'] has keys 'title' and 'pages', but no 'author'.

2. Step 2: Accessing missing key causes error

   Trying info['book']['author'] raises KeyError because 'author' is missing.

3. Final Answer:

   KeyError because 'author' key does not exist -> Option D

4. Quick Check:

   Missing key access = KeyError [OK]

Hint: Check if key exists before accessing nested dictionary [OK]

Common Mistakes:

• Assuming missing keys return None
• Confusing KeyError with SyntaxError
• Thinking nested dictionary keys are always present

5. Given this nested dictionary:

students = {
  'Alice': {'math': 90, 'science': 85},
  'Bob': {'math': 75, 'science': 95}
}

Which code correctly adds a new subject 'english' with score 88 for Alice?

hard

A. students['Alice']['english'] = 88

B. students['english']['Alice'] = 88

C. students['Alice'] = {'english': 88}

D. students['english'] = {'Alice': 88}

Solution

1. Step 1: Identify where to add new subject

   We want to add 'english' score inside Alice's dictionary.

2. Step 2: Add key-value pair inside nested dictionary

   Use students['Alice']['english'] = 88 to add the new subject and score.

3. Final Answer:

   students['Alice']['english'] = 88 -> Option A

4. Quick Check:

   Add key inside nested dict = students['Alice']['english'] = 88 [OK]

Hint: Add new key inside inner dictionary using outer then inner keys [OK]

Common Mistakes:

• Replacing entire inner dictionary instead of adding key
• Adding key at wrong dictionary level
• Swapping keys order