5 ms·
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
by echlebek 10y ago
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.
- malaggan 10y agoIt 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.
- sweezyjeezy 10y agoThat'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)...
- lorenzhs 10y agoNo, it means asymptotically equal to f(n). O(n^2 + n log n) = O(n^2), despite n log n not being a constant.
- PeCaN 10y agoWhile 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?