Какова временная сложность «set» и «if item in array» в Python?

Question

Мне нужно проверить, существует ли число и его двойник в массиве. Этот код с использованием setрешить это. Однако я не уверен, что временная сложность лучше, чем. Я использую for loop а также if 2*item in sкак показано ниже. Разве не для того, чтобы узнать, находится ли элемент в массиве, мы используем другой O(N). Что означает O(N^2)в итоге? Если это оптимально, как я могу реализовать коды на C без использования nested loop?
Большое спасибо!

        def checkIfExist(arr]) -> bool:
    s = set(array)
    for item in s:
        if 2 * item in s and item != 0:
            return True
    if arr.count(0) >= 2:
        return True
    return False

Answer 1

Временная сложность оператора in для наборов в python составляет в среднем O(1) и только в худшем случае O(N), поскольку наборы в python внутренне используют HashTable.

Таким образом, временная сложность вашей функции в среднем должна быть O(N) и только в худшем случае будет O(N^2), где N - длина массива.

Подробнее здесь https://wiki.python.org/moin/TimeComplexity