News for hackers. Stuff that matters.
Re:Probabilistic Filters By Example: Cuckoo Filter and Bloom... by echlebek on Tuesday July 19, 2016 @07:54PM (#12125838)
I'm a little confused by the Big-Oh notation O(2). In my CS classes we were taught that O(c) = O(1). So seeing something like 'O(1) to O(2)' is a bit odd.

But I love the visualization - it's very clear how things are working conceptually.

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?