Create various random numbers within a range

Question

I want to generate n different numbers between 1 and N (of course, n <= N). N can be very large. If n is very small, one efficient way generates numbers and compares them with the set we got to make sure that it is a new number. It takes O (n ^ 2) time and O (n) memory. If n is large enough, we can use the Shuffle Fisher-Yates algorithm to generate a random permutation (stop after n steps). It takes O (n) time, but we must also use O (N) memory.

That is the question. What can we do if we do not know how large n is? I hope the algorithm just uses O (n) memory and stops after O (n) time. Is it possible?

Answer 1

You can essentially do the same as for very small n, but just make this check more efficient. For example, a naive verification method, if you have already generated a number, is simply a linear search for a list of previously generated values. For unknown n, you can save a set of previously generated values, sorted so that you can use a more efficient search to identify duplicates. With a naive approach, the algorithm takes O (n ² ) time, but a more reasonable search from previous results can reduce this to O (n * log ₂ n).