Python "in" operator time complexity on range()

Question

I have the following function:

def foo(length, num):
  return num in range(length)

What's the time complexity of this function? Noting that range() creates a Range object on Python 3, will the time complexity of this function be O(1) or O(N)?

Would like to know whether there's a difference in time complexity between the various Python versions as well (2 vs 3).

Answer 1

In python-3.x a range(..) is an object, it does not construct a list. If you perform member checks with an int as item, then it can do that quite fast. The algorithm is a bit complicated, since there are both positive and negative steps. You can look it up on [GitHub]. A simple algorithm with a positive step count (c > 0) for x in range(a, b, c) is something like:

x ≥ a &wedge; x < b &wedge; mod(x-a, c) = 0.

For a negative step count (c < 0) is is quite similar:

x ≤ a &wedge; x > b &wedge; mod(x-a, c) = 0.

If we consider the comparisons to be done in O(1) and calculating the modulo as well, it is an O(1) algorithm. In reality for huge numbers, it scales in the number of digits of the numbers, so it is an O(log n) algorithm.

This however only works for ints. Indeed, in case you use floats, complex, other numerical or non-numerical types, it does not perform the above calculations. It will then fall back on iterating over the range(..) object. Which of course can take considerable time. If you have a range of a million elements, it will thus iterate over all these elements and eventually reach the end of the range, and return False, or find a match, and return True. In the future, perhaps some extra functionality can be implemented for some numerical types, but one can not do this in general, since you can define your own numerical type with an equality operation that works differently.

In python-2.x, range(..) is a function that returns a list. Indeed:

>>> range(15)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
>>> type(range(15))
<type 'list'>

In order to check if an element is a member of a list, it will iterate over the list, and check equality for all items until it finds an element that is equal, or the list is exhausted. If we consider checking if two items are equal to be constant time, then this takes linear time O(n). In reality for huge numbers, checking if two numbers are equal, scales linear with the number of "digits", so O(log m) with m the value of that number.

python-2.x has an xrange(..) object as well, but this does not check for membership with the above demonstrated trick.