The other answers do not talk about 2 crucial operations on sets: Unions and intersections. In the worst case, union will take O(n+m) whereas intersection will take O(min(x,y)) provided that there are not many element in the sets with the same hash. A list of time complexities of common operations can be found here: https://wiki.python.org/moin/TimeComplexity

I think set creation is taking most of the tim as it involves hashing each element, as mentioned by @tim-peters,.

Here, I have created set and list before performing a search operation and the search time seems to be a lot faster for sets than that of list.

import random
import timeit

def setup(n):
    data = list(range(n))
    random.shuffle(data)
    return set(data), data

def test_set(s, value):
    return value in s

def test_list(l, value):
    return value in l

n = 1000000
s, l = setup(n)

# Test with a value that's guaranteed to be in both
value_in = random.choice(l)

# Test with a value that's guaranteed not to be in either
value_out = n + 1

print("Searching for a value that exists:")
print("Set:", timeit.timeit(lambda: test_set(s, value_in), number=1000))
print("List:", timeit.timeit(lambda: test_list(l, value_in), number=1000))

print("\nSearching for a value that doesn't exist:")
print("Set:", timeit.timeit(lambda: test_set(s, value_out), number=1000))
print("List:", timeit.timeit(lambda: test_list(l, value_out), number=1000))

Result:

Searching for a value that exists:
Set: 0.00023545200008356915
List: 28.11379308300002

Searching for a value that doesn't exist:
Set: 0.0002436169999100457
List: 52.67750670600003