В среднем случае: list: - поиск по значению — O(n), требуется линейный просмотр. set: - проверка "x in my_set" — O(1) в среднем, т.к. используется хеш-таблица. dict: - доступ по ключу my_dict[key] — O(1) в среднем, также хеш-таблица. Важно: в худшем случае (много коллизий) операции с хеш-таблицей могут деградировать до O(n), но в реальной жизни такое встречается редко.