2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Jun 29 '17 at 21:37
  • $\begingroup$ @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? $\endgroup$ – amsquareb Jun 30 '17 at 7:26
  • $\begingroup$ No, that's fine -- both questions got answered, so all is well. $\endgroup$ – D.W. Jun 30 '17 at 15:22
3
$\begingroup$

You are asking excellent questions!

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.

The answer to your second question, about the time complexity of computing the hash function, is that it takes time linear in the size of the data item. Most hash functions used in this context are "rolling hash", in which a small has value is being updated as the data item is read. This ensures that the time complexity is indeed linear. Hash functions for such uses are designed with speed in mind, and so usually memory access is not an issue. The division operation at the end – if at all – is not too costly for modern CPUs, and can be avoided entirely if the size of the hash table is a power of 2.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ <<<Most hash functions used in this context are "rolling hash">>> - in which context?? If we are going through the data file extracting fixed-size strings, indeed we may use rolling hash, but the lookup/update operation is still O(l) since we need to compare the entire string once hash is matched. If we just insert a bunch of independent strings (say words from the file), we need to go through entire string to compute the hash. Of course, with binary tree we will get at least O(l + log n) complexity since we need to compare each key with l bytes of the string. $\endgroup$ – Bulat Aug 20 '18 at 19:51
1
$\begingroup$

Speed of calculating the hash function of large keys: You don't actually have to process the whole key. For example if the key is a string, you might process only the first and last 40 characters to calculate the hash function.

The biggest advantage of hashing vs. binary search is that it is much cheaper to add or remove an item from a hash table, compared to adding or removing an item to a sorted array while keeping it sorted. (Binary search trees work a bit better in that respect).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.