1. Big-O Efficiency of Python Dictionary Operators
One important side note on dictionary performance is that the efficiencies are for average performance.
| Operation | Big-O Efficiency |
| copy | O(n) |
| get item | O(1) |
| set item | O(1) |
| delete item | O(1) |
| contains (in) | O(1) |
| iteration | O(n) |
2. Comparison of time efficiency of in operator between list and dictionary
We will compare the performance of the contains operation between lists and dictionaries. We will confirm that the contains operator for lists is \(O(n)\) and the contains operator for dictionaries is \(O(1)\).
import timeit
import random
for i in range(10000, 1000001, 20000):
t = timeit.Timer(f"random.randrange({i}) in x", "from __main__ import random, x")
x = list(range(i))
lst_time = t.timeit(number=1000)
x = {j:None for j in range(i)}
d_time = t.timeit(number=1000)
print(f"{i}, {lst_time:.3f}, {d_time:.3f}")
We can see that the dictionary is consistently faster. And also can see that the time it takes for the contains operator on the list grows linearly with the size of the list while the time for the contains operator on a dictionary is constant even as the dictionary size grows.
Source from : https://runestone.academy/ns/books/published/pythonds/AlgorithmAnalysis/Dictionaries.html
