Flajolet–Martin algorithm ( Cardinality Estimation)
Jump to navigation
Jump to search
Time Complexity
$O(N)$
Space Complexity
$O(log n)$ words
(https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/pii/S0022000097915452)
Description
Approximate?
Approximate
Approximation Factor:
Randomized?
Yes,
Model of Computation
Word RAM
Year
1984