What assumptions can we safely make about the Java Collections shuffle(List<?>, Random) method?

Question

So I am looking into the collections shuffle method and trying to come up with a list of what is and is not ensured when we run it. There are some obvious cases I've come up which are the following:

1. The list given will contain the same elements after shuffling as before
2. The list may or may not be the same after running the method (you could end up with the same order of elements)
3. The method will run in linear time (I think that this is true but am not 100% positive).

Does this list sum it up or am I missing some possible cases?

Answer 1

The official documentation of Collections.shuffle has a lot to say about what will happen. The list will be shuffled using what seems to be the Fisher-Yates shuffle algorithm, which (assuming that random access is available in O(1)) runs in time O(n) and space O(1). The implementation will use space O(n) if random access isn't available. Assuming that the underlying random source is totally unbiased, the probability of any particular ordering occurring is equal (that is, you get a uniformly-random distribution over possible permutations).

So, to answer your questions:

1. The list will contain the same elements.
2. They're probably in a different order, but there's a 1 / n! chance than they'll be in the same order.
3. The runtime is O(n), and the space usage is either O(1) or O(n) depending on whether your list has random access support.