Skip to main content
Software Engineering

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

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 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? 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. 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). 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.) Commented Apr 20, 2016 at 11:07