It seems to me the probability of a false positive membership test is non-zero. | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		fauigerzigerk on Jan 18, 2009 \| parent \| context \| favorite \| on: Neat data structure: "Ullman" set It seems to me the probability of a false positive membership test is non-zero.

abecedarius on Jan 18, 2009 [–]

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.

fauigerzigerk on Jan 18, 2009 | [–]

Yes you're right. Thanks.

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