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?
Asked
Active
Viewed 3,656 times
4
Donbeo
- 15,655
- 32
- 99
- 175
1 Answers
7
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.
Martijn Pieters
- 963,270
- 265
- 3,804
- 3,187