Exercise 6.1

算法设计与分析

Problem

We consider another streaming problem:
Given a data stream $a_1,\cdots,a_m$, compute the number of distinct elements. That is, compute $|\{a_1,\cdots,a_m\}|$.
Show that any deterministric algorithm solving the above problem requires at least $n$ bits of memory.

Proof:

As we are going to compute $|\{a_1,\cdots,a_m\}|$, each element in the the data stream $a_1,\cdots,a_m$ should be count at least once.
That is, each element in $[n]$ could exactly have $2$ state: existed or empty.
Thus, we must have at least $2^n$ different states to solve this problem, i.e. the algorithm requires at least $n$ bits of memory.