What is the time complexity of checking membership in tuples?

Question

Time complexities for checking membership (x in data_structure) in dictionary, list, and set are listed here: http://wiki.python.org/moin/TimeComplexity

• dict - O(1)
• list - O(n)
• set - O(1)

But, I can't find the one for tuple in any of the Python documentation. I tried the following code to check for myself:

import time 

l = list(range(10000000))
t = tuple(range(10000000))
s = set(range(10000000))

start = time.perf_counter()  
-1 in s
elapsed = time.perf_counter() 
e = elapsed - start 
print("Time spent in set is: ", e)

start = time.perf_counter()  
-1 in l
elapsed = time.perf_counter() 
e = elapsed - start 
print("Time spent in list is: ", e)


start = time.perf_counter()  
-1 in t
elapsed = time.perf_counter() 
e = elapsed - start 
print("Time spent in tuple is: ", e)

I get something like this:

Time spent in set is:  2.0000000000575113e-06
Time spent in list is:  0.07841469999999995
Time spent in tuple is:  0.07896940000000008

Which tells me that it is O(n) as well. Can anyone confirm this? Is there an official documentation that confirms this?

Answer 1

Consider a tuple to be just a 'frozen list'. A tuple, like a list, has to be searched through entry by entry in order to find whether an object is a member of that tuple.

Complexity for a membership test is identical to that of a list: O(n).

The reason why dicts and sets are O(1) is that entries are accessed via a hashing algorithm.