Time Complexity: Why dictionaries are used
O(1)
0
0
Why dictionaries are used in Python - Performance Analysis
Understanding Time Complexity
We want to understand why dictionaries are chosen for certain tasks in Python.
How does using a dictionary affect the speed of finding or storing data?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
my_dict = {"apple": 3, "banana": 5, "orange": 2}
# Access a value by key
value = my_dict["banana"]
# Add a new key-value pair
my_dict["grape"] = 7
# Check if a key exists
exists = "apple" in my_dict
# Remove a key-value pair
del my_dict["orange"]
This code shows common dictionary operations: accessing, adding, checking, and deleting items by key.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Accessing or modifying items by key in the dictionary.
- How many times: Each operation happens once here, but in real use, these can happen many times.
How Execution Grows With Input
When the dictionary grows bigger, how does the time to find or add a key change?
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 1 step or less |
| 100 | About 1 step or less |
| 1000 | About 1 step or less |
Pattern observation: The time to find or add a key stays almost the same even if the dictionary gets bigger.
Final Time Complexity
Time Complexity: O(1)
This means looking up or changing a value by key takes about the same short time no matter how many items are in the dictionary.
Common Mistake
[X] Wrong: "Finding a value in a dictionary takes longer as the dictionary gets bigger."
[OK] Correct: Dictionaries use a special method that lets them find keys quickly without checking every item, so size does not slow them down much.
Interview Connect
Knowing why dictionaries are fast helps you choose the right tool for storing and finding data quickly in real projects.
Self-Check
"What if we changed the dictionary keys to be lists instead of strings? How would the time complexity change?"