Hyperloglog, Probability, Hash Function, Cardinality Estimation, Dynamic Programming.
get_trailing_zeros(q, u) g[r] = max(g[r], b) # Estimated cardinality w = sum(g)/m a = 0.79402*m*2**w print(a) For each input in the stream, the time complexity is now reduced to O(w) from O(m*w). The updated expected cardinality when we are using m buckets instead of m hashes can be written as