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

Worst case time complexity of inserting an element into hash table will be O(1), in case of chaining...Right?

---

@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)

---

@ashok7273
if all elements collide in the same place still we can push the element at the beginning of the list. which will take O(1) time.

---

Yes but for 'n' number of insertion...it wil take O(n) time

---

I think worst case insertion complexity will be $O(n^2)$ if duplicates are not allowed and it will $O(n)$ if duplicates are allowed.

Case 1 - Duplicates allowed :

Lets assume all the elements map to the same slot then for every element we can add it at the front of the chain.So $O(1)$ for each insertion and $O(n)$ for $n$ insertions. 

Case 2 - Duplicates not allowed:

Here also all the elements map to the same slot :

Now for $1^{st}$ element we insert it to the slot it maps to.

For $2^{nd}$ element (it also maps to the same slot as said earlier) we need to do lookup whether it is already present or not - So 1 comparison is needed and then it is inserted in $O(1)$ time at the front of the chain if not already present.

For $3^{rd}$ element again do lookup , so 2 comparisons and then it is inserted in $O(1)$ time.

For $4^{th}$ element again do lookup , so 3 comparisons and then it is inserted in $O(1)$ time.

$\cdots$ 

$\cdots$ 

$\cdots$

For $n^{th}$ element again do lookup , so $n-1$ comparisons and then it is inserted in $O(1)$ time.

So total time of insertion of $n$ elements = total lookup time + total insert time.

Total lookup time = $1+2+3+...+(n-1)=\frac{n(n-1)}{2}=O(n^2)$

Total insert time $= O(n)$

Total Insertion time for $n$ elements $= O(n^2)+O(n)=O(n^2)$

---

@Sourajit25 why are you assuming these kinds of special constraints?

---

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.