Flajolet-Martin Algorithm

Flajolet-Martin algorithm approximates the number of unique objects in a stream or a database in one pass. If the stream contains  elements with  of them unique, this algorithm runs in  time and needs  memory. So the real innovation here is the memory usage, in that an exact, brute-force algorithm would need  memory (e.g. think “hash map”).