Почему проверка наличия элемента во множестве и в списокe проходит за разное время?

потому что в списке (массиве), чтобы проверить наличие элемента надо просмотреть все (!!!) элементы, т.е. потратить O(n) времени (линейное время)

а в множестве, чтобы чтобы понять индекс элемента в котором хранится элемент можно вычислить хэш от элемента

index = hash(value)

в этом случае поиск элемента будет занимать константное время O(1)

В множестве как и в словаре проверка производится по хэшу элемента (ключа для словаря), который хитрым образом преобразуется в адрес элемента в памяти. На случай если происходит коллизия, и у разных элементов оказывается одинаковый хэш, есть механизм разрешения коллизий. В простейшем случае - это список элементов с одинаковым хэшем, в котором дальше идёт поиск. В целом при небольшом числе коллизий поиск во множестве и в словаре по ключу имеет сложность О(1).
А вот при поиске в списке нужно последовательно перебрать его элементы, пока не найдётся нужный, это уже сложность О(n).