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?