Big O notation of randomness

Question

I was thinking about inefficient algorithms based on randomness and wondered how to categorise them.

For instance. Say you wanted to generate all the numbers from 1 to N in a random order but only once each.

My inefficient algorithm does this...

Generate a random number between 1 and N (inclusive).
Check it has not already been used.
If it has then generate a new random number until you get one that hasn't been used.
Display the random number.
Store random number in checking array.

This should get all the numbers in a random order but for large values of N will have to run multiple times when getting the last few numbers.

For instance. On average the last random value will take N times to generate.

Best case for this is O(N) because there is a possibility that each random number generated is distinct.

Average case is a bit harder...

Without properly going into the calculation I think it's O(NlogN) or possible O(N^2).

But what would the worst case be? Well, worst case is that it never finds all the numbers. It would loop infinitely and never actually complete. For large N that's understandable but how do you give the big O notation for it?

Answer 1

The worst-case is O(∞). The best-case is Ω(n²), because you have to generate n numbers, and for each number generated you have to search a list of length n whether or not the number is already in there.

Answer 2

I would say that this problem would be solved using probabilistic analysis. So you would need to consider the probability that a random number selected was already in the list. In order to do this you may need to make an assumption about your random number generator, specifically that it generates numbers with a uniform distribution, meaning any number from 1 to N was equally likely to be generated.

So for the first number selected the probability that it has already been selected is 0/n = 0, since nothing is in the list yet. The second number the probability that the number has already been selected is 1/n. This would continue with each generated number. Additionally you'd need to associate costs with each of these probabilities. You'd need to consider both the costs associated with the probability that the number has already been selected as well as the cost associated with the probability that it has not.

Answer 3

If you want to create an array, you can use a slightly modified algorithm which runs in O (n).

Fill the array with the numbers from 1 to n. 
Repeat for i = 0 to n - 1:
    Generate a random number r such that 0 ≤ r < n - i.
    Exchange array [i] and array [i + r]