3 ms·
It never halts under the condition of infinitely small probability. So it never never halts.
by heavenlyblue 8y ago
It never halts under the condition of infinitely small probability. So it never never halts.
- Sharlin 8y agoYeah, the worst case is more of a limit. If you're really unlucky the algorithm can take an arbitrarily long time to halt.
- bo1024 8y agoMeasure 0 and "never" are subtly different. There do exist sets of random draws for which the algorithm never halts. The probability of getting such a draw is zero, but they exist. It's like picking a random number uniformly between 0 and 1 (in theory, not on a discrete computer). Getting 2 is impossible, never happens. Getting say 1.5 has probability 0, but it is possible.
- deleted 8y ago[deleted]
- Sharlin 8y ago(Getting 0.5 I think you mean :)
- bo1024 8y agoRight, thanks
- heavenlyblue 8y agoWell, for the starts - I said it was an "infinitely small probability" (just as you've said it's zero), so I said "never" because it's more of a practical question. With the same logic you can say that sha-256 is easily reversible by iterating over all possible mappings from sha256(z) to x. But it isn't. Purely because of the sheer scale of that number. And to be clear: reversing sha-256 under the condition of sha-256 being a perfect hash function is the same as drawing 256 zeros from a purely random function. The best way to go about the complexity of this algorithm is the runtime density function, where the total number of samples defines how many additional (false) iterations we'd need to do on average.