3 ms·
The very rough rule of thumb that I think one should remember is: You get a 50% chance of collision with sqrt(total) samples. Sqrt(1 000 000) = 1 000, close en
by codeflo 2y ago
The very rough rule of thumb that I think one should remember is: You get a 50% chance of collision with sqrt(total) samples.
Sqrt(1 000 000) = 1 000, close enough to the exact number you calculated.
- ColinWright 2y agoMore accurately, for 50% it's \sqrt(\ln(4))\sqrt(N) which is \sqrt( ln(4) N ). That's about 1.17741 times \sqrt(N). The reasons are explained here: https://news.ycombinator.com/item?id=40886363 https://news.ycombinator.com/item?id=40886363