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.

Answer 3

Runtime is O(1) if this source code example is still relevant.

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

I would believe it is due to Oracle's explaination on how they generate random numbers in this page.

An instance of this class is used to generate a stream of pseudorandom numbers. The class uses a 48-bit seed, which is modified using a linear congruential formula. (See Donald Knuth, The Art of Computer Programming, Volume 2, Section 3.2.1.)