Timeline for Big O notation of randomness
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 26, 2016 at 21:59 | history | edited | user22815 | CC BY-SA 3.0 |
Proper notation for best case is Big-Omega (Ω)
|
| Apr 20, 2016 at 11:07 | comment | added | Scheintod | 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.) | |
| May 14, 2015 at 19:23 | vote | accept | Fogmeister | ||
| May 14, 2015 at 13:52 | comment | added | Jörg W Mittag | @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). | |
| May 14, 2015 at 13:38 | comment | added | user40980 | @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. | |
| May 14, 2015 at 9:26 | comment | added | Brandin | 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? | |
| May 14, 2015 at 9:24 | vote | accept | Fogmeister | ||
| May 14, 2015 at 10:11 | |||||
| May 14, 2015 at 9:24 | comment | added | Fogmeister | 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 | |
| May 14, 2015 at 9:05 | history | answered | Jörg W Mittag | CC BY-SA 3.0 |