3

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?

Improve this question
8
  • How long does it take for you to check if the generated random number has already been used
    – Brandin
    Commented May 14, 2015 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
    Commented May 14, 2015 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
    Commented May 14, 2015 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
    Commented May 14, 2015 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
    Commented Apr 20, 2016 at 10:06

3 Answers 3

Reset to default
5

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.

Improve this answer
5
  • 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
    Commented May 14, 2015 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
    Commented May 14, 2015 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
    Commented May 14, 2015 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
    Commented May 14, 2015 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
    Commented Apr 20, 2016 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.

Improve this answer
3
  • 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
    Commented Apr 20, 2016 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
    Commented Apr 26, 2016 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
    Commented Apr 26, 2016 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]
Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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