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
  • 15,655
  • 32
  • 99
  • 175

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
  • 963,270
  • 265
  • 3,804
  • 3,187