CODEWITHSUNDEEP
performancealgorithmhashmapchainingasymptotic-complexity
user4129542
user4129542

Reputation: 329

Average cost of successful search in hash table in chaining

I have searched every where for this but I can't understand why is it O(1+a/2) where a is the load factor. Can some one explain this step by step.

Upvotes: 2

Views: 1607

Answers (1)

amit
amit

Reputation: 178411

Let the number of elements in your hash table be n.
It means there are n/a total number of cells (/lines) in the hash table, each holds a list of elements. This is the definition of load factor.

So, the expected number of elements assossiated to each such cell is n/(n/a) = a.
A linear search in an unsorted list needs to traverse half of the elements until it finds the correct one on average (and we assume it is a succesful search), so it needs to traverse a/2 elements.

The 1 factor comes from accessing the correct list in the hash table itself.

Upvotes: 2

Related Questions