Dictionary comprehension with condition in Python - Time & Space Complexity

Time Complexity: Dictionary comprehension with condition

O(n)

Understanding Time Complexity

We want to understand how the time needed to build a dictionary using comprehension with a condition changes as the input grows.

Specifically, how does filtering items while creating a dictionary affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

numbers = range(1, n+1)
filtered_dict = {x: x*x for x in numbers if x % 2 == 0}

This code creates a dictionary of squares for even numbers from 1 to n.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each number from 1 to n.
• How many times: Exactly n times, once for each number.

How Execution Grows With Input

As n grows, the code checks each number once and sometimes adds it to the dictionary.

Input Size (n)	Approx. Operations
10	About 10 checks and up to 5 insertions
100	About 100 checks and up to 50 insertions
1000	About 1000 checks and up to 500 insertions

Pattern observation: The number of checks grows directly with n, but insertions happen only for half the numbers (even ones).

Final Time Complexity

Time Complexity: O(n)

This means the time to build the dictionary grows in a straight line with the size of the input.

Common Mistake

[X] Wrong: "Because we only add half the items, the time is O(n/2), which is faster than O(n)."

[OK] Correct: Even though fewer items are added, the code still checks every number once, so the overall time still grows linearly with n.

Interview Connect

Understanding how filtering affects time helps you explain your code clearly and shows you can think about efficiency in everyday tasks.

Self-Check

"What if we changed the condition to check for prime numbers instead of even numbers? How would the time complexity change?"