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?
Best Answer
The worst-case is O(∞). The best-case is Ω(n2), 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.