CODEWITHSUNDEEP
algorithmdata-structureshashtablecomplexity-theorybig-o
mavix
mavix

Reputation: 2552

Worst-case and best-case time for populating a hash table using chaining?

Obviously best-case is O(n), but apparently the worst-case is O(n2), which I don't understand. If you implement the hash table as an array of linked lists, I assume the worst case is where every hash goes to the same place.

So isn't putting each item still O(1), since adding an item to a linked list is just a matter of sticking a node on the end/front? And in the worst case, you end up with an array of empty buckets + one bucket of size n? What am I missing here?

Upvotes: 2

Views: 1729

Answers (1)

jpalecek
jpalecek

Reputation: 47762

I guess they assume an implementation that does check for the presence of an element in the hash table before inserting (which is typical, since hashtables usually represent sets in theory). That implementation would have to check each element of the list before inserting a new element.

Upvotes: 4

Related Questions