1

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?

  • How long does it take for you to check if the generated random number has already been used – Brandin May 14 '15 at 9:02
  • @Brandin I hadn't thought about that. I guess you would use a hash to store them so it would be constant time for checking if the random number has been used. – Fogmeister May 14 '15 at 9:03
  • Are you worried that you will happen to generate an already used number a significant amount of time? Have you calculated how likely this is to actually happen? – Brandin May 14 '15 at 9:11
  • Well for calculating the last number it will create repeat numbers an average of N-1 times before getting the last distance value. They are only stored once though. Does not store the repeated random values. – Fogmeister May 14 '15 at 9:12
  • 1
    @JoulinRouge I'm well aware of the Fisher-Yates shuffle :) this was more of an interesting topic rather than a practical way of generating a list of random numbers :) – Fogmeister Apr 20 '16 at 10:06
4

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.

  • Ah, cool. I didn't know about O(infinite) so wasn't sure what to use. The checking could be constant time though so O(n) is best case. :-) thanks – Fogmeister May 14 '15 at 9:24
  • 2
    This answer doesn't seem to take likelihood into account. Maybe infinite time is possible, but extremely unlikely. If you analyze randomized algorithms normally you must take the likelihood into account. For example, if you've got an algorithm with an infinite-time case, but this case only happens 0.00001% of the time, maybe that's acceptable for an application. Then you've also got to consider the security and quality of the random number generation - can an adversary an discover which particular case results in you doing infinite work? – Brandin May 14 '15 at 9:26
  • @Brandin the worst case is you keep picking random numbers such that they've already been selected previously. Some seeds for prngs may be shorter than expected. If you have such a situation and have already generated all the numbers in the period, you will encounter O(∞) on the next iteration. – user40980 May 14 '15 at 13:38
  • 1
    @Brandin: the question wasn't about expected worst-case, it was about worst-case. Yes, the probability that the worst-case happens is almost zero, but it can happen. The probability that randomized quick sort hits a bad pivot every time is also almost zero, still, it has worst-case complexity of O(n²), even if it has an expected worst-case of O(n*log n). – Jörg W Mittag May 14 '15 at 13:52
  • 1
    No. You don't have to search a list. You could mark already found numbers trivially in an array in form: A[ number ] = true/false. (I think "checking array" in the question can be read as such if you like.) – Scheintod Apr 20 '16 at 11:07
1

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.

  • There is no randomness involved. With Big-Oh we assume the algorithm performs as poorly as it can at each step, which gives us the upper bound. The accepted answer is correct. – user22815 Apr 20 '16 at 4:35
  • I know with Big-Oh randomness is not an issue. He asked about average case 'expected case' in which case we should take into account the randomness of the number generator – JBurk94 Apr 26 '16 at 21:52
  • Question is ambiguous. There is no "average case" in standard asymptotic notation. If there were, it would not be Big-O (worst case). – user22815 Apr 26 '16 at 21:57
0

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]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.