What is the time complexity of random.nextInt() in Java?

I'm wondering what the time complexity of random.nextInt() is in Java.

I will attach a snippet of code down below:

Random rand = new Random(); List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5)); int[] randomNums = new int[list.size()]; int i = 0; while(i < randomNums.length) { int index = rand.nextInt(list.size()); randomNums[i++] = list.get(index); list.remove(index); } return randomNums; 

1 Answer

Random.nextInt() calls Random.next(32) which is implemented as:

protected int next(int bits) { long oldseed, nextseed; AtomicLong seed = this.seed; do { oldseed = seed.get(); nextseed = (oldseed * multiplier + addend) & mask; } while (!seed.compareAndSet(oldseed, nextseed)); return (int)(nextseed >>> (48 - bits)); } 

This is a Linear congruential generator which generates a new pseudo-random number using a single equation.

In practice the complexity here is O(1) because compareAndSet in the while condition will loop only if multiple threads are accessing the same Random instance. This should be avoided by design, as per the Random class javadoc:

Instances of java.util.Random are threadsafe. However, the concurrent use of the same java.util.Random instance across threads may encounter contention and consequent poor performance. Consider instead using java.util.concurrent.ThreadLocalRandom in multithreaded designs.