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

Practice

1. What does the following code do?
for key in my_dict:

easy

A. Iterates over the keys of the dictionary

B. Iterates over the values of the dictionary

C. Iterates over the key-value pairs as tuples

D. Raises a syntax error

Solution

1. Step 1: Understand the for loop syntax

   The loop uses for key in my_dict, which by default iterates over dictionary keys.

2. Step 2: Identify what is accessed in each iteration

   Each iteration gives one key from the dictionary, not values or pairs.

3. Final Answer:

   Iterates over the keys of the dictionary -> Option A

4. Quick Check:

   for key in dict = keys [OK]

Hint: for key in dict loops over keys only [OK]

Common Mistakes:

• Thinking it loops over values
• Confusing keys with key-value pairs
• Assuming it raises an error

2. Which of the following is the correct syntax to iterate over keys and values in a dictionary my_dict?

easy

A. for key, value in my_dict.keys():

B. for key, value in my_dict:

C. for key in my_dict.values():

D. for key, value in my_dict.items():

Solution

1. Step 1: Recall dictionary methods for iteration

   To get keys and values, use my_dict.items() which returns key-value pairs.

2. Step 2: Check syntax correctness

   Only for key, value in my_dict.items(): correctly unpacks keys and values.

3. Final Answer:

   for key, value in my_dict.items(): -> Option D

4. Quick Check:

   Use dict.items() for keys and values [OK]

Hint: Use dict.items() to get keys and values together [OK]

Common Mistakes:

• Using my_dict without .items() for key-value pairs
• Trying to unpack keys() or values() which return single elements
• Syntax errors from missing .items()

3. What is the output of this code?

my_dict = {'a': 1, 'b': 2}
for k, v in my_dict.items():
    print(k, v)

medium

A. a 1\nb 2

B. ('a', 1)\n('b', 2)

C. a\nb

D. 1\n2

Solution

1. Step 1: Understand the loop over items()

   The loop unpacks each key-value pair from my_dict.items().

2. Step 2: Analyze the print statement

   It prints the key and value separated by space on each line, so output lines are "a 1" and "b 2".

3. Final Answer:

   a 1\nb 2 -> Option A

4. Quick Check:

   print(k, v) prints key and value separated by space [OK]

Hint: print(k, v) shows key and value separated by space [OK]

Common Mistakes:

• Expecting tuples printed instead of separate values
• Printing only keys or only values
• Confusing output format with list or tuple

4. Find the error in this code:

my_dict = {'x': 10, 'y': 20}
for key, value in my_dict:
    print(key, value)

medium

A. Dictionary keys cannot be unpacked

B. Incorrect print statement syntax

C. Missing .items() after my_dict

D. No error, code runs fine

Solution

1. Step 1: Identify the iteration target

   The loop tries to unpack two variables from my_dict directly, which yields only keys.

2. Step 2: Correct the iteration method

   To unpack key and value, use my_dict.items() instead of just my_dict.

3. Final Answer:

   Missing .items() after my_dict -> Option C

4. Quick Check:

   Use my_dict.items() to unpack key, value [OK]

Hint: Use .items() to unpack key and value in loop [OK]

Common Mistakes:

• Trying to unpack keys only without .items()
• Assuming dict directly yields key-value pairs
• Ignoring error message about unpacking

5. Given the dictionary data = {'a': 0, 'b': 2, 'c': 0, 'd': 4}, which code snippet creates a new dictionary with only keys having non-zero values?

hard

A. new_dict = {k: v for k, v in data if v != 0}

B. new_dict = {k: v for k, v in data.items() if v != 0}

C. new_dict = {k: v for k in data.keys() if data[k] != 0}

D. new_dict = {k: v for v, k in data.items() if v != 0}

Solution

1. Step 1: Understand dictionary comprehension with condition

   We want to keep only items where value is not zero, so use if v != 0 in comprehension.

2. Step 2: Check correct unpacking and syntax

   new_dict = {k: v for k, v in data.items() if v != 0} correctly unpacks key and value from data.items() and filters by value.

3. Final Answer:

   new_dict = {k: v for k, v in data.items() if v != 0} -> Option B

4. Quick Check:

   Use dict.items() and filter with if condition [OK]

Hint: Use dict.items() with if condition in comprehension [OK]

Common Mistakes:

• Forgetting .items() when unpacking key and value
• Swapping key and value in unpacking
• Using keys() without accessing values