Count-distinct problem: Difference between revisions

Revision as of 08:52, 13 November 2024

Revision as of 09:06, 13 November 2024

Line 86:

{{nowrap|If <math> u \leq p </math> then}}

Insert <math> (a_t, u) </math> into {{mvar|B}}

{{nowrap|While <math> |B| = s \wedge u < p </math> then}}

Remove every element of <math>(a', B u')</math> withof probability{{mvar|B}} with <math> u' > \frac{1p}{2} </math>

{{nowrap|<math> p \leftarrow \frac{p}{2} </math>}}

{{nowrap|End While}}

If <math> u < p </math> then

Insert <math> (a_t, u) </math> into {{mvar|B}}

{{nowrap|End For}}

{{nowrap|return <math> |B| / p </math>.}}