Time complexity of in function in python

Question

I would like to check whether x in list(y), hence I use the code

if x in y:
   return True

what is the time complexity? is it O(1) or O(n)?

Thank you

Answer 1

It depends on what type of object y is.

If y is a sequence type like list or tuple, the time complexity is O(n), because Python has to scan the sequence looking for a match.

If y is a hashed type like a set or dict, the time complexity is typically O(1), because Python can immediately check whether a matching object exists in the hash table.

Update: the question was edited to indicate that y is a list. In that case, the time complexity is O(n).

Also see this duplicate question and more background info.