News for hackers. Stuff that matters.
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.