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 4,129 times
4

Donbeo
- 17,067
- 37
- 114
- 188
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
- 1,048,767
- 296
- 4,058
- 3,343