De fato, considerando apenas o objeto do tipo range
, o tempo para verificar se um determinado valor pertence ao intervalo é, na notação big-O, O(1), que significa que será constante independente do tamanho do espaço verificado, o que explica os tempos de ambos os testes serem iguais. E a explicação para isso é bem simples: matematicamente é muito fácil verificar se um número pertence a um intervalo.
TL;DR
A solução mais básica que consigo imaginar para verificar se um número está em um determinado intervalo é percorrer todos os elementos deste intervalo, comparando um a um com o valor que estou verificando e, se caso encontrar um igual, retornar verdadeiro, caso contrário, falso.
def pertence(sequencia, valor):
for item in sequencia:
if item == valor:
return True
return False
Com certeza uma solução assim jamais seria O(1), na verdade seria O(n), o que poderia justificar tempos pequenos para intervalos pequenos, mas não justificaria o mesmo para intervalos grandes. Então como é possível?
Matematicamente, podemos dizer que o número x
pertence ao intervalo [A, B[
se, e somente se, x
for maior ou igual a A
e x
for menor que B
. Isto é:

Toda essa mágica acontece no objeto range
graças à implementação do método __contains__
, que é implicitamente invocado através do operador in
. E, além de verificar se o valor de x
é maior ou igual a A
e menor a B
, quando definido o passo do intervalo, será necessário também verificar se o valor coincide com o passo. Por exemplo, se eu defino o objeto range(0, 10, 2)
, estarei pegando os valores pares de 0 a 10 e, desta forma, o número 3 não pertencerá ao intervalo, mesmo que seja maior que 0 e menor que 10. Assim, a implementação em Python seria semelhante à:
class range:
def __contains__(self, x):
if not self.A <= x < self.B:
return False
if self.passo is not None:
return (x - self.A) % self.passo == 0
return True
Desta forma, a verificação não depende mais do tamanho do intervalo, mas sim de um número constante de operações, o que caracteriza ser uma solução O(1).

Veja funcionando no Repl.it
Porém, a classe range
do Python pertence ao módulo builtins
, que é implementada em C, não em Python. Ou seja, embora a lógica seja a mesma, o código que é executado, de fato, para verificar se o valor pertence ao intervalo é outro. A título de curiosidade, é possível acessar o repositório oficial do CPython e verificar a implementação em C, mas especificamente entre as linhas 337 e 379:
static int
range_contains_long(rangeobject *r, PyObject *ob)
{
int cmp1, cmp2, cmp3;
PyObject *tmp1 = NULL;
PyObject *tmp2 = NULL;
int result = -1;
/* Check if the value can possibly be in the range. */
cmp1 = PyObject_RichCompareBool(r->step, _PyLong_Zero, Py_GT);
if (cmp1 == -1)
goto end;
if (cmp1 == 1) { /* positive steps: start <= ob < stop */
cmp2 = PyObject_RichCompareBool(r->start, ob, Py_LE);
cmp3 = PyObject_RichCompareBool(ob, r->stop, Py_LT);
}
else { /* negative steps: stop < ob <= start */
cmp2 = PyObject_RichCompareBool(ob, r->start, Py_LE);
cmp3 = PyObject_RichCompareBool(r->stop, ob, Py_LT);
}
if (cmp2 == -1 || cmp3 == -1) /* TypeError */
goto end;
if (cmp2 == 0 || cmp3 == 0) { /* ob outside of range */
result = 0;
goto end;
}
/* Check that the stride does not invalidate ob's membership. */
tmp1 = PyNumber_Subtract(ob, r->start);
if (tmp1 == NULL)
goto end;
tmp2 = PyNumber_Remainder(tmp1, r->step);
if (tmp2 == NULL)
goto end;
/* result = ((int(ob) - start) % step) == 0 */
result = PyObject_RichCompareBool(tmp2, _PyLong_Zero, Py_EQ);
end:
Py_XDECREF(tmp1);
Py_XDECREF(tmp2);
return result;
}
O parâmetro r
representa o próprio objeto range
e o parâmetro ob
representa o valor a ser verificado. O objeto r
possui os campos start
, stop
e step
que representam o início, final e passo do intervalo. Embora seja uma implementação maior, a lógica é exatamente a apresentada anteriormente em Python.
Na implementação em C, também é possível verificar que o objeto r
não é modificado em momento algum, o que implica que o gerador que é definido por range
não será modificado ao verificar se o valor pertence ao intervalo. Por ser um gerador e, por definição, gerador poder ser iterado apenas uma vez, seria catastrófico se o operador in
percorresse o range
, pois o intervalo não teria mais utilidade depois disso. Perceba que estamos tratando aqui apenas do objeto range
e suas peculiaridades, o que não implica em ser assim com todos os geradores do Python.
intervalo = range(10)
if 5 in intervalo:
for i in intervalo:
print(i)
Veja funcionando no Repl.it