Complexity of Hashing

Question

How do we find out the average and the worst case time complexity of a Search operation on Hash Table which has been Implemented in the following way:

Let's say 'N' is the number of keys that are required to be hashed. We take a hash table of size M (M=alpha*N, alpha ~ 0.1). Collisions are resolved by storing the keys in a chained linked list fashion, storing each new entry at the head of each linked list pointed to by 'hashTable[i]'.

IMHO, the best , avg and worst case complexities could be O(1), O(N/M) and O(N). Correct me if I am wrong. A detailed explanation would be appreciated.

Answer 1

The answer depends on the characteristics of the hashing function, and the particular value of alpha. The worst case occurs if the hash achieves poor distribution (for any alpha), and as you stated in your original post, is O(N). The best case occurs when you have a well-distributed hash and alpha is relatively large (>1.0), and as you said, that is O(1). So we agree on the best case and worst case.

However I think the average case needs more analysis, because alpha has a non-linear effect on performance. Consider two extreme examples. Case 1, alpha = 100, 1000, 10000. As alpha scales to infinity, you will have no avoidable collisions (i.e. those caused by having to truncate hashes to map into M buckets, as opposed to non-uniform behavior of the hash), and so the average case converges to the best case, or O(1). Case 2, alpha = 0.01, 0.001, 0.0001. As alpha scales to zero, you have fewer and fewer hash buckets until the entire table is just one hash bucket with all values in a single list in that bucket, and so the average case converges to the linear-search worst case, or O(N).

The average case is between O(1) and O(N), depending on alpha. We could express this as O(N^x), where x is a function that maps alpha = 0 to x = 1, and alpha = infinity to x = 0. So for the sake of debate, (see http://en.wikipedia.org/wiki/Heaviside_function), maybe something like O(N^(e^(-alpha))).