Para qual complexidade algorítmica de tempo a expressão será executada?

Выражение 999999 in range(1, 99999999) в Python выполняется за O(1) по времени.

Это связано с тем, что объект range в Python реализован как ленивый генератор с арифметической прогрессией, и оператор in для него не перебирает все элементы, а вычисляет принадлежность по формуле.

Например, для проверки, входит ли число x в range(start, stop), Python проверяет, что start <= x < stop и что (x - start) % step == 0. Это делается за константное время без перебора всех элементов.