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