Assume we know a parameter $n\in\mathbb N$, and then get to observe a sequence of elements $x_1,\ldots, x_n$, one at a time.Our goal is to count the number of distinct elements in $x_1,\ldots, x_n$, and succeed with probability $1-\epsilon$.A simple approach would be to compute a $\log\left({n\choose 2}\epsilon^{-1}\right)$ bits fingerprint of each element, and then count the number of distinct fingerprints.Since the number of distinct elements is a most $n$, with probability of at least $1-\epsilon$, all fingerprints of distinct elements will be different.This gives us a total of $\approx n\log (n^2\epsilon^{-1})-n$ bits of space.But is this anywhere close to optimal? Can we perhaps use only $O(n\log\epsilon^{-1})$ bits for the problem? What would be a lower bound for this problem?EDIT: I'm specifically interested in computing the number of distinct elements exactly, with high probability, and not in approximation algorithms.In the paper An Optimal Algorithm for the Distinct Elements Problem, the authors give a $O(\gamma^{-2}+\log n)$ bits algorithm for computing a $(1+\gamma)$ approximation with high probability, and claim that this is optimal.However, setting $\gamma<n^{-1}$ for getting exact count with high probability gives a $\Omega(n^2)$ bits algorithm, which seems worse than the $O(n\log n)$ proposed above.They do not assume that $n$ is known in advance, which may explain this difference.
How much memory is needed for counting distinct elements in a stream exactly with high probability
ds.algorithms;lower bounds;data streams