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

Practice

1. Which of the following is the correct way to create an empty dictionary in Python?

easy

A. my_dict = ()

B. my_dict = []

C. my_dict = {}

D. my_dict = ''

Solution

1. Step 1: Understand dictionary syntax

   Dictionaries in Python are created using curly braces {}.

2. Step 2: Identify the empty dictionary

   An empty dictionary is represented as {}, not square brackets, parentheses, or quotes.

3. Final Answer:

   my_dict = {} -> Option C

4. Quick Check:

   Empty dictionary = {} [OK]

Hint: Use curly braces {} for dictionaries, brackets [] for lists [OK]

Common Mistakes:

• Using [] which creates a list, not a dictionary
• Using () which creates a tuple, not a dictionary
• Using '' which creates an empty string

2. Which of the following is the correct syntax to create a dictionary with keys 'a' and 'b' and values 1 and 2 respectively?

easy

A. my_dict = ['a':1, 'b':2]

B. my_dict = {'a'=1, 'b'=2}

C. my_dict = ('a':1, 'b':2)

D. my_dict = {'a':1, 'b':2}

Solution

1. Step 1: Check dictionary key-value pair syntax

   Dictionary pairs use colon : between key and value inside curly braces.

2. Step 2: Identify correct syntax

   my_dict = {'a':1, 'b':2} uses curly braces and colons correctly. Options A and C use wrong brackets, and D uses equals sign which is invalid.

3. Final Answer:

   my_dict = {'a':1, 'b':2} -> Option D

4. Quick Check:

   Dictionary pairs use : inside {} [OK]

Hint: Use colons : between keys and values inside {} [OK]

Common Mistakes:

• Using square brackets [] instead of curly braces {}
• Using parentheses () instead of curly braces {}
• Using equals sign = instead of colon :

3. What will be the output of the following code?

my_dict = {1: 'one', 2: 'two', 3: 'three'}
print(my_dict[2])

medium

A. 'two'

B. KeyError

C. 2

D. 'one'

Solution

1. Step 1: Understand dictionary key lookup

   Accessing my_dict[2] retrieves the value for key 2.

2. Step 2: Find value for key 2

   Key 2 maps to the string 'two' in the dictionary.

3. Final Answer:

   'two' -> Option A

4. Quick Check:

   my_dict[2] = 'two' [OK]

Hint: Dictionary[key] returns the value for that key [OK]

Common Mistakes:

• Confusing keys and values
• Expecting the key itself as output
• Mistaking KeyError when key exists

4. The following code throws an error. What is the problem?

my_dict = {1: 'one', 2: 'two', 3: 'three'}
print(my_dict[4])

medium

A. Key 4 does not exist in the dictionary

B. Syntax error in dictionary creation

C. Values must be integers, not strings

D. Dictionary keys must be strings

Solution

1. Step 1: Check dictionary keys

   The dictionary has keys 1, 2, and 3 only.

2. Step 2: Accessing a missing key

   Trying to access my_dict[4] causes a KeyError because key 4 is not present.

3. Final Answer:

   Key 4 does not exist in the dictionary -> Option A

4. Quick Check:

   Accessing missing key causes KeyError [OK]

Hint: Check if key exists before accessing dictionary [OK]

Common Mistakes:

• Assuming all keys exist
• Confusing syntax error with runtime error
• Thinking keys must be strings

5. You want to create a dictionary from two lists: keys = ['name', 'age', 'city'] and values = ['Alice', 30, 'NY']. Which code correctly creates this dictionary?

hard

A. my_dict = {keys: values}

B. my_dict = {keys[i]: values[i] for i in range(len(keys))}

C. my_dict = dict(keys, values)

D. my_dict = dict(zip(values, keys))

Solution

1. Step 1: Understand dictionary creation from two lists

   We need to pair each key with its corresponding value by index.

2. Step 2: Analyze options

   my_dict = {keys[i]: values[i] for i in range(len(keys))} uses dictionary comprehension with index to pair keys and values correctly. my_dict = dict(keys, values) is invalid syntax. my_dict = {keys: values} creates a dictionary with one key (the list) which is invalid. my_dict = dict(zip(values, keys)) reverses keys and values.

3. Final Answer:

   my_dict = {keys[i]: values[i] for i in range(len(keys))} -> Option B

4. Quick Check:

   Use dict comprehension with index to pair keys and values [OK]

Hint: Use dict comprehension with index or zip() to pair keys and values [OK]

Common Mistakes:

• Using dict() with two lists directly
• Swapping keys and values in zip()
• Using list as a key