7 votes 7 votes Consider a hash table with chaining scheme for overflow handling: What is the worst-case timing complexity of inserting $n$ elements into such a table? For what type of instance does this hashing scheme take the worst-case time for insertion? Algorithms gate1990 hashing algorithms descriptive + – makhdoom ghaya asked Nov 25, 2016 • edited Nov 26, 2016 by $ourav makhdoom ghaya 2.4k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
6 votes 6 votes 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. Aakash Das answered Nov 25, 2016 Aakash Das comment Share Follow See all 9 Comments See all 9 9 Comments reply Show 6 previous comments Sourajit25 commented Dec 24, 2019 reply Follow Share 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 0 votes 0 votes Kiyoshi commented Jun 4, 2021 reply Follow Share @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... 2 votes 2 votes John_Smith commented Jan 2 reply Follow Share Extending @Sourajit25‘s comment, I believe the answer for this question would be –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)\).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. 0 votes 0 votes Please log in or register to add a comment.