O(log N) == O(1) - Why not?

Solution 1:

Big O notation tells you about how your algorithm changes with growing input. O(1) tells you it doesn't matter how much your input grows, the algorithm will always be just as fast. O(logn) says that the algorithm will be fast, but as your input grows it will take a little longer.

O(1) and O(logn) makes a big diference when you start to combine algorithms.

Take doing joins with indexes for example. If you could do a join in O(1) instead of O(logn) you would have huge performance gains. For example with O(1) you can join any amount of times and you still have O(1). But with O(logn) you need to multiply the operation count by logn each time.

For large inputs, if you had an algorithm that was O(n^2) already, you would much rather do an operation that was O(1) inside, and not O(logn) inside.

Also remember that Big-O of anything can have a constant overhead. Let's say that constant overhead is 1 million. With O(1) that constant overhead does not amplify the number of operations as much as O(logn) does.

Another point is that everyone thinks of O(logn) representing n elements of a tree data structure for example. But it could be anything including bytes in a file.

Solution 2:

I think this is a pragmatic approach; O(logN) will never be more than 64. In practice, whenever terms get as 'small' as O(logN), you have to measure to see if the constant factors win out. See also

Uses of Ackermann function?

To quote myself from comments on another answer:

[Big-Oh] 'Analysis' only matters for factors that are at least O(N). For any smaller factor, big-oh analysis is useless and you must measure.

and

"With O(logN) your input size does matter." This is the whole point of the question. Of course it matters... in theory. The question the OP asks is, does it matter in practice? I contend that the answer is no, there is not, and never will be, a data set for which logN will grow so fast as to always be beaten a constant-time algorithm. Even for the largest practical dataset imaginable in the lifetimes of our grandchildren, a logN algorithm has a fair chance of beating a constant time algorithm - you must always measure.

EDIT

A good talk:

http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey

about halfway through, Rich discusses Clojure's hash tries, which are clearly O(logN), but the base of the logarithm is large and so the depth of the trie is at most 6 even if it contains 4 billion values. Here "6" is still an O(logN) value, but it is an incredibly small value, and so choosing to discard this awesome data structure because "I really need O(1)" is a foolish thing to do. This emphasizes how most of the other answers to this question are simply wrong from the perspective of the pragmatist who wants their algorithm to "run fast" and "scale well", regardless of what the "theory" says.

EDIT

See also

http://queue.acm.org/detail.cfm?id=1814327

which says

What good is an O(log2(n)) algorithm if those operations cause page faults and slow disk operations? For most relevant datasets an O(n) or even an O(n^2) algorithm, which avoids page faults, will run circles around it.

(but go read the article for context).

Solution 3:

This is a common mistake - remember Big O notation is NOT telling you about the absolute performance of an algorithm at a given value, it's simply telling you the behavior of an algorithm as you increase the size of the input.

When you take it in that context it becomes clear why an algorithm A ~ O(logN) and an algorithm B ~ O(1) algorithm are different:

if I run A on an input of size a, then on an input of size 1000000*a, I can expect the second input to take log(1,000,000) times as long as the first input

if I run B on an input of size a, then on an input of size 1000000*a, I can expect the second input to take about the same amount of time as the first input

EDIT: Thinking over your question some more, I do think there's some wisdom to be had in it. While I would never say it's correct to say O(lgN) == O(1), It IS possible that an O(lgN) algorithm might be used over an O(1) algorithm. This draws back to the point about absolute performance above: Just knowing one algorithm is O(1) and another algorithm is O(lgN) is NOT enough to declare you should use the O(1) over the O(lgN), it's certainly possible given your range of possible inputs an O(lgN) might serve you best.