2,430 views
0 votes
0 votes
If we are inserting an element in chaining(outside) hashing technique, then what will be the time complexity in best case, average case and Worst case.

1 Answer

2 votes
2 votes
If we are using chaining technique for collision resolution in hashing, then the minimum chain length will be 1 (not zero, since then there will be no chain). The maximum chain length will be Ο(n) since we can have all the elements in one slot. An example of this worst case could be: hash function h(k) = k mod 10 and the elements as 2,12, 22, 32, 42, 52, 62, 72, 82, 92

The average case would be an average of all the intermediate cases, (best case + worst case)/2 i.e., Ο(n).

This is the time complexity for the chaining element access.

Related questions

0 votes
0 votes
1 answer
2
nandini gupta asked Jan 22, 2017
644 views
A hash table of length 100 uses chaining.What is the probability that all the values are hashed into the same slot after 5 insertions?
0 votes
0 votes
1 answer
3
0 votes
0 votes
1 answer
4
Himanshu1 asked Dec 16, 2015
743 views