Is a dictionary membership check in python a linear operation as in O(n)? For instance:
Dct = {"a":0,"b":1,"c":2,"d":3}
if d in Dct:
#do something
Asked
Active
Viewed 156 times
0
DannyMoshe
- 6,023
- 4
- 31
- 53
-
1Duplicate of [Time complexity of accessing a Python dict](http://stackoverflow.com/q/1963507) ? – Bhargav Rao Jun 22 '16 at 16:18
-
1**TL;DR**: nope, `O(1)` on average. – jonrsharpe Jun 22 '16 at 16:19
1 Answers
2
No.
A dict is implemented as a hash table therefore the hash calculation takes time and the lookup is just O(1).
The dict also optimizes itself automatically regarding the memory size in order to prevent large buckets.
For more info regarding hash tables, you may see the Wikipedia article.
Bharel
- 23,672
- 5
- 40
- 80