Re^4: rand + shift || pop

[JavaFan]

Actually, the expected running time of splicing is Ω(n), as a random splice will have to move n/4 elements on average.

If you want to repeatedly get a random element (without duplication), shuffle the array and use pop or shift, for a linear running time. Repeatedly splicing a random element has an expected running time of Ω(n²).