3 ms·
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
by PeCaN 10y ago
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.
- bdupras 10y agoGuilty. 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.
- bdupras 10y agoTo 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?