Dictionary creation in Python - Time & Space Complexity

Time Complexity: Dictionary creation

O(n)

Understanding Time Complexity

When we create a dictionary in Python, it is important to know how the time to build it grows as we add more items.

We want to understand how the work changes when the number of items increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

my_dict = {}
for i in range(n):
    my_dict[i] = i * 2

This code creates a dictionary by adding n key-value pairs, where each key is a number and the value is twice that number.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding one item to the dictionary inside the loop.
• How many times: This happens once for each number from 0 up to n-1, so n times.

How Execution Grows With Input

As we increase n, the number of times we add items grows directly with n.

Input Size (n)	Approx. Operations
10	10 additions
100	100 additions
1000	1000 additions

Pattern observation: The work grows in a straight line as n grows. Double n, double the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to create the dictionary grows directly with the number of items we add.

Common Mistake

[X] Wrong: "Adding each item to a dictionary takes longer and longer as the dictionary grows."

[OK] Correct: Python dictionaries are designed to add items quickly, so each addition takes about the same time regardless of size.

Interview Connect

Understanding how dictionary creation scales helps you explain how data structures behave in real programs, a useful skill in many coding discussions.

Self-Check

"What if we used a list of tuples and converted it to a dictionary all at once? How would the time complexity change?"