CODEWITHSUNDEEP
time-complexityhashtableload-factor
Rrmm
Rrmm

Reputation: 53

Time complexity of search operation on hash tables using separate chaining

It's usually said that on average the cost of the search operation on a hash table is O(1) because the length of a given list on the table is proportional to the load factor. What I don't get is that the load factor clearly depends on the number of entries we want to store so it is not necessarily a constant. Suppose we are frequently adding new entries, doesn't that make the length of an average list depend on the number of entries too? How is the operation O(1)?

Sorry for my english. It's not my main language.

Upvotes: 0

Views: 688

Answers (1)

Joni
Joni

Reputation: 111219

Many implementations resize the table so that the load factor stays bounded by a constant. Resize takes time proportional to number of items stored, but if done infrequently enough it balances out so that insertions take amortized constant time.

Upvotes: 2

Related Questions