4

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?

Donbeo
  • 17,067
  • 37
  • 114
  • 188

1 Answers1

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