What is O(n) for java.util.Random.next(n)

Question

I want to know whether java.util.Random.next(n) scales linearly with n or is a constant? Could someone help me with this or show me how to go about determining the complexity?

Answer 1

From the docs:

Random.nextInt(n) uses Random.next() less than twice on average- it uses it once, and if the value obtained is above the highest multiple of n below MAX_INT it tries again, otherwise is returns the value modulo n (this prevents the values above the highest multiple of n below MAX_INT skewing the distribution), so returning a value which is uniformly distributed in the range 0 to n-1.

According to the docs the java.util.Random.next is implemented as follows

synchronized protected int next(int bits) {
   seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
   return (int)(seed >>> (48 - bits));
 }

So the complexity is O(1)

On a side note:-

You can use several tools which are there to measure the complexity with a micro-benchmark. You can find a list over here. However if the runtime complexity is important to you you can use the Fast Mersenne Twister.(This is an external library to measure the runtime complexity as Javas random number generators are quite fast, but statistically bad)

Answer 2

The Javadoc of next explains

The method next is implemented by class Random by atomically updating the seed to

(seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)

and returning

(int)(seed >>> (48 - bits))

Clearly, there is no trace of O(n) complexity in these expressions.