Basic dictionary comprehension in Python - Time & Space Complexity

Time Complexity: Basic dictionary comprehension

O(n)

Understanding Time Complexity

We want to see how the time needed to create a dictionary using comprehension changes as the input grows.

How does the work increase when we have more items to process?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

numbers = [1, 2, 3, 4, 5]
squares = {x: x * x for x in numbers}

This code creates a new dictionary where each number is paired with its square.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each item in the list to compute and add a key-value pair.
• How many times: Once for each item in the input list.

How Execution Grows With Input

As the list gets bigger, the number of steps grows in a straight line with the number of items.

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

Pattern observation: Doubling the input roughly doubles the work needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to build the dictionary grows directly with the number of items you start with.

Common Mistake

[X] Wrong: "Dictionary comprehension is faster than a loop, so it must take less time as input grows."

[OK] Correct: Both dictionary comprehension and loops do the same work for each item, so time grows the same way with input size.

Interview Connect

Understanding how dictionary comprehension scales helps you explain your code's efficiency clearly and confidently.

Self-Check

"What if we added a nested loop inside the dictionary comprehension? How would the time complexity change?"

Practice

1. What does the following dictionary comprehension do?
{x: x*x for x in range(3)}

easy

A. Creates a list of squares from 0 to 2

B. Creates a set of squares from 0 to 2

C. Creates a dictionary with numbers 0 to 2 as keys and their squares as values

D. Creates a dictionary with keys as squares and values as numbers

Solution

1. Step 1: Understand the loop and key-value pairs

   The comprehension loops over numbers 0, 1, 2 and uses each number as the key.

2. Step 2: Calculate the value for each key

   Each value is the square of the key (x*x), so values are 0, 1, 4 respectively.

3. Final Answer:

   Creates a dictionary with numbers 0 to 2 as keys and their squares as values -> Option C

4. Quick Check:

   Dictionary comprehension = key: x, value: x*x [OK]

Hint: Look for key:value pairs inside braces with a for loop [OK]

Common Mistakes:

• Confusing dictionary with list or set comprehension
• Mixing keys and values in comprehension
• Thinking it creates a list instead of a dictionary

2. Which of the following is the correct syntax for a dictionary comprehension that creates keys from 1 to 3 and values as their double?

easy

A. [x: 2*x for x in range(1, 4)]

B. {x: 2*x for x in range(1, 4)}

C. {x => 2*x for x in range(1, 4)}

D. (x: 2*x for x in range(1, 4))

Solution

1. Step 1: Identify correct dictionary comprehension syntax

   Dictionary comprehensions use curly braces with key:value pairs and a for loop inside.

2. Step 2: Check each option

   {x: 2*x for x in range(1, 4)} uses curly braces and colon correctly. Options B, C, D use wrong brackets or arrow syntax.

3. Final Answer:

   {x: 2*x for x in range(1, 4)} -> Option B

4. Quick Check:

   Curly braces + key:value + for loop = correct syntax [OK]

Hint: Remember dictionary comprehension uses curly braces and colon [OK]

Common Mistakes:

• Using square brackets instead of curly braces
• Using arrow (=>) instead of colon for key-value
• Using parentheses which create generator expressions

3. What is the output of this code?

nums = [1, 2, 3]
squares = {n: n**2 for n in nums if n % 2 != 0}
print(squares)

medium

A. {1: 1, 3: 9}

B. {2: 4}

C. {1: 1, 2: 4, 3: 9}

D. {}

Solution

1. Step 1: Understand the filtering condition

   The comprehension includes only numbers where n % 2 != 0, meaning odd numbers only (1 and 3).

2. Step 2: Calculate squares for filtered numbers

   Squares are 1*1=1 and 3*3=9, so dictionary is {1:1, 3:9}.

3. Final Answer:

   {1: 1, 3: 9} -> Option A

4. Quick Check:

   Filter odd numbers and square them = {1:1, 3:9} [OK]

Hint: Check the if condition filters keys before squaring [OK]

Common Mistakes:

• Including even numbers by mistake
• Confusing list comprehension output with dictionary
• Ignoring the if condition in comprehension

4. Find the error in this dictionary comprehension:

result = {x, x*2 for x in range(3)}

medium

A. Missing colon between key and value

B. Using parentheses instead of curly braces

C. Range function is incorrect

D. No error, code is correct

Solution

1. Step 1: Check syntax for key-value pairs

   Dictionary comprehension requires a colon ':' between key and value, but here a comma ',' is used.

2. Step 2: Confirm other parts are correct

   Curly braces and range(3) are correct, so the error is the missing colon.

3. Final Answer:

   Missing colon between key and value -> Option A

4. Quick Check:

   Key:value pairs need colon, not comma [OK]

Hint: Use colon ':' to separate key and value in dict comprehension [OK]

Common Mistakes:

• Using comma instead of colon between key and value
• Confusing set comprehension with dictionary comprehension
• Using wrong brackets for comprehension

5. Given a list of words, create a dictionary comprehension that maps each word to its length but only include words longer than 3 letters.
Which code correctly does this?

words = ['cat', 'house', 'dog', 'elephant']

hard

A. {word: len(word) for word in words where len(word) > 3}

B. {word: len(word) for word in words if word > 3}

C. {word: len(word) if len(word) > 3 for word in words}

D. {word: len(word) for word in words if len(word) > 3}

Solution

1. Step 1: Understand filtering condition syntax

   The if condition must come after the for loop to filter words by length correctly.

2. Step 2: Check each option's syntax

   {word: len(word) for word in words if len(word) > 3} correctly places 'if len(word) > 3' after the for loop. Others have syntax errors or wrong condition placement.

3. Final Answer:

   {word: len(word) for word in words if len(word) > 3} -> Option D

4. Quick Check:

   Filter after for loop with if condition [OK]

Hint: Put if condition after for loop in dictionary comprehension [OK]

Common Mistakes:

• Placing if condition before for loop
• Using invalid syntax like 'where' instead of 'if'
• Comparing word string directly to number