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

Question

I want to know if the java.util.Random.next(n) ruler scaled with n or is a constant? Can someone help me with this or show me how to determine 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 resulting value is higher than the maximum n is less than MAX_INT, it tries again, otherwise the value modulo n is returned (this prevents values ​​above itself high multiple of n below MAX_INT, distorting the distribution), therefore, a return value that is evenly distributed in the range from 0 to n-1.

According to docs 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 that can be measured using the micro benchmark. You can find the list here . However, if execution complexity is important to you, you can use Fast Mersenne Twister . (This is an external library for measuring the complexity of execution in the form of Javas random number generators are pretty fast, but statistically bad)

Answer 2

Javadoc next explains

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

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

and returning

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

It is clear that in these expressions there is no trace of complexity O (n).

Answer 3

The runtime is O(1) if this sample source code still matters.

  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 that because of Oracle's explanation of how they generate random numbers on this page .

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