what is the time complexity to check if a dictionary has a key?
dictionary, python, time-complexity
Solution
Membership testing has the exact same cost as retrieving an item, so O(1).
That's only logical, because in order to return the value of a given key, you first need to determine if it is in the dictionary. If retrieving a key takes constant time, then determining if it is in the dictionary in the first place can only ever take constant time, too.
Problem
According to https://wiki.python.org/moin/TimeComplexity given a dictionary `D` the operation `D[k]` is constant. What is the complexity of `k in D` ? Is this still constant?