Re:Probabilistic Filters By Example: Cuckoo Filter and Bloom...
by malaggan on Tuesday July 19, 2016 @08:06PM
(#12125895)
It would seem that the author of the article is abusing the Big-O notation. When saying some operation is O(f(n)) they probably mean that the operation takes exactly f(n) steps, rather than the usual meaning of asymptotic complexity.
Re:Probabilistic Filters By Example: Cuckoo Filter and Bloom...
by sweezyjeezy on Wednesday July 20, 2016 @05:44AM
(#12127807)
That's not true, O(f(n)) means at most f(n) up to a constant. If you wanted to say something took exactly f(n), surely you would just write f(n)...
Re:Probabilistic Filters By Example: Cuckoo Filter and Bloom...
by lorenzhs on Wednesday July 20, 2016 @06:46AM
(#12128039)
No, it means asymptotically equal to f(n). O(n^2 + n log n) = O(n^2), despite n log n not being a constant.
Re:Probabilistic Filters By Example: Cuckoo Filter and Bloom...
by PeCaN on Wednesday July 20, 2016 @12:51AM
(#12126970)
While you're right, sometimes people (mis)use it to avoid hiding the constants.
O(2) is a weird one, but say O(5n) can be useful, if not technically correct. I guess O(2) is vaguely useful wrt Cuckoo hashing and filters to denote the 2 lookups.
Re:Probabilistic Filters By Example: Cuckoo Filter and Bloom...
by bdupras on Wednesday July 20, 2016 @07:18PM
(#12133301)
Guilty. I wanted to be up-front about the constant factor of 1 or 2. I was tired when I wrote that and was actually looking at cleaning that up a couple days ago, but got distracted. Soon.
Re:Probabilistic Filters By Example: Cuckoo Filter and Bloom...
by bdupras on Wednesday July 20, 2016 @08:22PM
(#12133634)
To further clarify, if a Bloom filter query is O(K) where k is the number of hash functions, then when k=7, the filter could be described as O(1).
The constant factors here are important for practical use. Hashing 7 times is significantly different than hashing 1 or 2 times.
For the original commenter, give me a suggestion if you don't mind. How would you expect to see that info depicted in a comparison chart so that it's honest and obvious?
But I love the visualization - it's very clear how things are working conceptually.