Skip to content

dict() Function Complexity

The dict() function creates dictionaries from various sources.

Complexity Analysis

Case Time Space Notes
Empty dict O(1) O(1) dict()
From keyword arguments O(n) avg, O(n^2) worst O(n) n = number of kwargs
From list of pairs O(n) avg, O(n^2) worst O(n) n = number of pairs
From another dict O(n) avg, O(n^2) worst O(n) n = dict size
From iterable of pairs O(n) avg, O(n^2) worst O(n) n = number of pairs

Basic Usage

Create Empty Dictionary

# O(1)
d = dict()  # {}

From Keyword Arguments

# O(n) - where n = number of kwargs
d = dict(a=1, b=2, c=3)
# {'a': 1, 'b': 2, 'c': 3}

d = dict(name="Alice", age=30, city="NYC")
# {'name': 'Alice', 'age': 30, 'city': 'NYC'}

From List of Pairs

# O(n) - where n = number of pairs
d = dict([("a", 1), ("b", 2), ("c", 3)])
# {'a': 1, 'b': 2, 'c': 3}

d = dict([("x", 10), ("y", 20)])
# {'x': 10, 'y': 20}

From Another Dictionary

# O(n) - where n = dict size
original = {"a": 1, "b": 2}
copy = dict(original)  # {'a': 1, 'b': 2} - shallow copy

# Copy entire dict
d = dict({"x": 10, "y": 20})
# {'x': 10, 'y': 20}

From zip() of Keys and Values

# O(n) - combine two iterables
keys = ["a", "b", "c"]
values = [1, 2, 3]

d = dict(zip(keys, values))
# {'a': 1, 'b': 2, 'c': 3}

Complexity Details

Hashing and Insertion

# O(n) - insert n key-value pairs
# Each pair requires:
# 1. Hash the key - O(1) average
# 2. Store the pair - O(1) average
# Total: O(n)

pairs = [("a", 1), ("b", 2), ("c", 3), ("d", 4)]
d = dict(pairs)  # O(4) - hash and store each pair

Collision Handling

# Average case: O(n)
# Pathological collisions can degrade construction toward O(n^2)

# Worst case: many keys map to the same hash/probe sequence

pairs = [(i, i*10) for i in range(1000)]
d = dict(pairs)  # O(n) average

Keyword Arguments

# O(n) - where n = number of kwargs
# Each keyword becomes a key-value pair

d = dict(a=1, b=2, c=3, d=4, e=5)  # O(5)

# More kwargs = slower
many = dict(**{f"key_{i}": i for i in range(100)})  # O(100)

Common Patterns

Convert Pairs to Dictionary

# O(n) - general conversion
pairs = [("Alice", 25), ("Bob", 30), ("Charlie", 35)]
ages = dict(pairs)
# {'Alice': 25, 'Bob': 30, 'Charlie': 35}

# From enumerate
items = ["a", "b", "c"]
indexed = dict(enumerate(items))
# {0: 'a', 1: 'b', 2: 'c'}

Combine Lists into Dictionary

# O(n) - using zip
names = ["Alice", "Bob", "Charlie"]
scores = [85, 92, 78]

results = dict(zip(names, scores))
# {'Alice': 85, 'Bob': 92, 'Charlie': 78}

Dictionary Copying

# All O(n) - shallow copy
original = {"a": 1, "b": 2}

copy1 = dict(original)          # O(n)
copy2 = original.copy()         # O(n) - same
copy3 = {**original}            # O(n) - unpacking

# All create shallow copies

Merge Dictionaries

# O(n + m) - where n, m = dict sizes
dict1 = {"a": 1, "b": 2}
dict2 = {"c": 3, "d": 4}

merged = dict(**dict1, **dict2)  # O(n+m)
# {'a': 1, 'b': 2, 'c': 3, 'd': 4}

# Or using update - also O(n+m)
merged = dict(dict1)
merged.update(dict2)

Performance Patterns

Keyword Arguments vs Pairs

# Both O(n), but different syntax

# Keyword arguments - limited to valid identifiers
d1 = dict(a=1, b=2, c=3)  # O(3)

# List of pairs - any hashable key
d2 = dict([("a", 1), ("b", 2), ("c", 3)])  # O(3)

# Speed similar, but pairs allow any key
d3 = dict([(1, "a"), (2, "b"), (None, "c")])  # O(3)

From Multiple Sources

# O(n) - combine kwargs and pairs
pairs = [("x", 10), ("y", 20)]
d = dict(pairs, z=30)  # O(3) - combine both
# {'x': 10, 'y': 20, 'z': 30}

Batch Creation

# O(n) - create all at once is faster than gradual

# Fast - O(n)
data = dict([(f"key_{i}", i) for i in range(100)])

# Slower - O(n) with overhead
data = {}
for i in range(100):
    data[f"key_{i}"] = i

# Preferably use dict() or comprehension
data = {f"key_{i}": i for i in range(100)}  # O(n)

Practical Examples

Parse Configuration

# O(n) - convert pairs to config dict
config_pairs = [
    ("timeout", 30),
    ("retries", 3),
    ("debug", True),
]

config = dict(config_pairs)
# {'timeout': 30, 'retries': 3, 'debug': True}

Map Names to Values

# O(n) - create mapping
names = ["Alice", "Bob", "Charlie"]
values = [1, 2, 3]

mapping = dict(zip(names, values))
# {'Alice': 1, 'Bob': 2, 'Charlie': 3}

# Useful for CSV data
headers = ["name", "age", "city"]
row = ["Alice", 30, "NYC"]
record = dict(zip(headers, row))
# {'name': 'Alice', 'age': 30, 'city': 'NYC'}

Create Lookup Table

# O(n) - build lookup from data
items = ["apple", "banana", "cherry"]
lookup = dict(enumerate(items))
# {0: 'apple', 1: 'banana', 2: 'cherry'}

# Or reverse
reverse_lookup = {v: k for k, v in lookup.items()}
# {'apple': 0, 'banana': 1, 'cherry': 2}

Initialize with Defaults

# O(n) - create with initial values
keys = ["a", "b", "c", "d"]
initial_value = 0

# Using dict comprehension
defaults = {k: initial_value for k in keys}  # O(n)

# Or with dict() - but requires pairs
defaults = dict((k, initial_value) for k in keys)  # O(n)

# defaultdict is O(1) for access, but setup is similar
from collections import defaultdict
defaults = defaultdict(int)  # O(1) setup, O(1) per access

Edge Cases

Empty Dictionary

# O(1)
d = dict()       # {}
d = dict([])     # {}
d = dict({})     # {}

Single Pair

# O(1)
d = dict([("a", 1)])   # {'a': 1}
d = dict(a=1)          # {'a': 1}

Duplicate Keys

# O(n) - last value wins
pairs = [("a", 1), ("a", 2), ("a", 3)]
d = dict(pairs)  # {'a': 3} - last value

# Same with kwargs
d = dict(a=1, b=2, a=3)  # {'a': 3, 'b': 2}

Non-hashable Keys

# O(n) - error for non-hashable keys
try:
    pairs = [([1, 2], "value")]  # Lists not hashable
    d = dict(pairs)  # TypeError
except TypeError:
    pass

Large Dictionaries

# O(n) - scales linearly
pairs = [(i, i*10) for i in range(10**6)]
d = dict(pairs)  # O(10^6) - creates large dict

Dictionary Comprehension Alternative

# All O(n), but different syntax

# Using dict()
d1 = dict([("a", 1), ("b", 2), ("c", 3)])

# Using dict comprehension - often preferred
d2 = {k: v for k, v in [("a", 1), ("b", 2), ("c", 3)]}

# Using dict() with zip
keys = ["a", "b", "c"]
values = [1, 2, 3]
d3 = dict(zip(keys, values))

# All O(n), comprehension often cleaner

Shallow vs Deep Copy

# dict() creates shallow copy
inner = {"x": 1}
outer = {"a": inner}

copied = dict(outer)
copied["a"]["x"] = 999  # Affects original!
# outer['a']['x'] is now 999

# For deep copy
import copy
deep = copy.deepcopy(outer)  # Doesn't affect original

Best Practices

✅ Do:

  • Use dict comprehensions for clarity: {k: v for ...}
  • Use dict() with zip() for pairs: dict(zip(keys, values))
  • Specify all data upfront if possible
  • Use keyword arguments for simple dicts

❌ Avoid:

  • Building dicts gradually with assignments
  • Assuming dict() is faster than {} (similar)
  • Confusing shallow and deep copies
  • Using non-hashable keys

Version Notes

  • Python 2.x: dict() works with iterables
  • Python 3.x: Preserves insertion order (3.7+)
  • All versions: Shallow copy by default