Hacker News new | ask | show | jobs
by fauigerzigerk 6354 days ago
It seems to me the probability of a false positive membership test is non-zero.
1 comments
abecedarius 6354 days ago
No, it's correct -- you can see that by induction on the add operation. If you're allowed to increase n without first ensuring the invariant on the first n members, then it can break, yes.
link
fauigerzigerk 6354 days ago
Yes you're right. Thanks.
link