[qyph]

Hyperloglog analyses generally assume access to the full data stream, and so are O(n) at a minimum. Perhaps by running hyperloglog on a sublinear sample of the dataset you'd get an algorithm in this class.

[doormatt]

That makes sense, thanks for explaining!