Two efficient algorithms for random sampling without replacement

Abstract

Hash-storage technique is applied when designing two new algorithms for random sampling without replacement. By the first algorithm a sample of M different elements out of N possible is found in expected 0(M) time with an auxiliary storage of 2M elements. The worst 2 case processing time is 0(M ²). By the second algorithm the average processing time is 0(M) and an array of only M elements is needed. The processing time in the worst case is for this algorithm unbounded.