GATE CSE 1990 | Question: 13b

Question

Consider a hash table with chaining scheme for overflow handling:

1. What is the worst-case timing complexity of inserting $n$ elements into such a table?
2. For what type of instance does this hashing scheme take the worst-case time for insertion?

Answer 1

1.) The worst case can be O(n) if all the insertions collide at the same key.

2.) This happens when we are not using an uniformly distributed hash function or when our hash table has only a single key where all the elements are chained up.

Comments

These are the constraints that we have to consider while insertion.Check the algo for insertion into hash table with chains : - http://faculty.cs.niu.edu/~freedman/340/340notes/340hash.htm

---

@ashok7273 @Sourajit25 @Verma Ashish

In case of chaining insertion of one element takes O(1) time

So in worst case ,for 'n' elements....T(n)=O(n)

why this is only true for worst case just think about it. It is true for average and best case also.

we have n elements which we want to insert in hash table. It doesn’t matter if we are inserting the same cell or different cells. Each insertion take O(1) time then why only for worst case it is true for average or best case also. 

anyone verify I’m saying correct or not...

---

Extending @Sourajit25‘s comment, I believe the answer for this question would be –

1. If duplicates are allowed, then every insertion takes \(\Theta(1)\) time (as we can simply insert every element at the head of the list pointed to by the slot it hashes to). So, inserting \(n\) elements takes \(\Theta(n)\) time. This is the same for every instance of hash table, hash function, input, etc. And, for every such instance, \(T_{worst\ case}=T_{average\ case}=T_{best\ case}=\Theta(n)\).
2. If duplicates are not allowed, then \(T_{worst\ case}=\Theta(n^2)\), as pointed out in @Sourajit25‘s comment. This can happen only when all the elements hash to the same slot, because no matter how well behaved your hash function is, or no matter how big your hash table is (since, theoretically speaking, it can be as large as possible), if we keep the hash function static throughout the execution of any algorithm (which I believe is usually the case), and use chaining to handle collisions, then there always exists some sequence of keys that hash to the same slot for any setup that we choose. It’s just that we console ourselves with the fact that the probability of that (those) particular input sequence(s) occurring is very small, but it’s still greater than zero.