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?
Big O notation of randomness
algorithms;random;algorithm analysis;big o
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.