do the in statement iterates over a dictionary in python?

Simon Ernesto Cardenas Zarate 0
Viewed 32

Say I have the following dictionary:

mydict = {
  "a": 1,
  "b": 2,
  "c": 3
}

are these the same in complexity?

return mydict.get("a", None) is not None
return "a" in mydict

I assume they still need to iterate over the dictionary, since if I want to look for key: "d", I would need to check all keys whether it exists or not, so both operations are O(n).

a follow up question is, does the same apply for lists? Say I have:

mylist = [1,2,3,4,5]

does

5 in mylist

also iterates over the whole list to find the number? I am asking because I saw this leetcode answer: https://www.code-recipe.com/post/two-sum in which 2 nested for loops is not preferred, but a for loop, and an in check, is way faster, but to me it sounds like both are doing nested loops.

time-complexity dictionary list python
1 Answers
return mydict.get("a", None) is not None
return "a" in mydict

Technically speaking, checking wether a key exists or not in a dictionnary is constant time O(1), because of how Hash works, you directly know wether the key exists or not

Now if you want to be precise, mydict.get("a", None) is not None is a tad slower than "a" in mydict

Because for the first one you verify if the key is in the dictionnary, then you return either the key or None, and then verify the equality, while in the 2nd one, you just verify if the key is in the dictionnary or not

It might seem like not much, but on very big data it can make a difference since comparison is slow in CPython

Sparkling Marcel0
Related