Hacker News new | past | comments | ask | show | jobs | submit login

The precise statement is that you need to have O(2^(N/2)) items before the probability of finding a hash collision is greater than 50% (or whatever nontrivial percentage). English is hard and I think whoever cares about the details can look it up themselves.



> I think whoever cares about the details can look it up themselves

Your statement was an incredibly common and often repeated misperception of probability and circumstance. Someone looking it up for themselves, as you suggest, is more likely than not to encounter dozens of wrong statements on the subject before they ever find a right one. I think it behooves us to not add more misinformation to the pile.


The precise statement should be Omega, not O, since you're doing a lower-bound.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: