# How exactly Hashing performs better than a Binary Search?

The time complexity of a Binary Search is O(log n) and Hashing is O(1) - so I've read. I have also read that Hashing outperforms Binary search when input is large, for example in millions. But I see that log n, when n is around 30 million, is roughly equal to 25.

If for such a large value of n, log n is just 25, then isn't O(log n) roughly the same as O(1)? Because O(1), basically means that the time complexity is constant. So, it could be bigger than or same as 25!?!(here I am assuming that the coefficient of log n, in the actual time usage/consumption function for Binary Search, is less than or equal to 1)

A related question I have, is regarding the calculation of time complexity of a hash algorithm. In all the literature, I barely find any mention of the time complexity of the hash function used and the division required thereafter(to calculate the index of the bucket).

So, exactly how do memory reads/access and computing a fairly complex mathematical operation(as in hash function), compete against each other, w.r.t. time consumption? One memory read/access roughly equates to what kind of basic mathematical operation, in terms of performance?

• Welcome to CS.SE! We prefer that you ask only one question per post. It sounds like you have two different questions, which should probably be posted in two separate posts. For the first one, cs.stackexchange.com/q/57814/755 is semi-relevant. For the second one, there's no single answer -- it depends on the hash function, and the best way to measure the cost of a hash function is probably to benchmark it. You might also want to read about the memory hierarchy and the latency of memory accesses. – D.W. Jun 29 '17 at 21:37
• @D.W. Thanks, I will keep that in mind. Bdw, do you want me to edit this question so as to delete second part and post it as a separate question? – amsquareb Jun 30 '17 at 7:26
• No, that's fine -- both questions got answered, so all is well. – D.W. Jun 30 '17 at 15:22

The answer to your first question, regarding the difference between $O(\log n)$ and $O(1)$, is that whereas binary search scales with the size of the array, searching for an item in a hash table scales with the size of the data item, which we often think of as constant. In practice, calculating the hash also takes time (as you also mention), and so to know which data structure has better performance, we need to empirically compare implementations of both data structures.