What is Big-O runtime of the standard random number generator in python? (Worst-case)

Question

Sample python2 code:

for i in range(N):
    print str(random.randint(0, N))

Is it safe to assume that the random number generator runs in O(1), so that the above loop (which simply prints N random numbers in the range from 0 - N) is O(N) ?

Answer 1

random.randint(0, N) is probably O(log N) i.e., it is proportional to number of bits in N.

The implementation confirms it if we assume that .getrandbits(k) is O(k).

It seems to be true for CPython if genrand_int32() is O(1). The source (for Mersenne Twister PRNG implementation) suggests that it is.