Why is a successful search in a chained hash table have a time complexity of Θ(1+(n/m)) on average?

Question

I get why an unsuccessful search in a chained hash table has a time complexity of Θ(1+(n/m)) on average, because the expected number of elements examined in an unsuccessful search is (n/m), and the total time required (including the time for computing hashFunction(key)) is Θ(1+(n/m)). But why is it the same for a successful search?

Answer 1

According to "Algorithms: Design and Analysis" by Cormen et al. expected number of key comparisons during successful search in a hash table with separate chaining collision resolution is 1 + α/2 - α/2n [where α=n/m]. Intuitive explaination: since this is a successful search, we check at least one key (we search for it), and a half of the rest keys in a chain.

Time complexity: Θ(1 + 1 + α/2 - α/2n) = Θ(1 + α), by definition of big-theta notation.

Answer 2

For a Successful search

NOTATION: α= n/m = load factor

A) MATHEMATICAL PROOF

1)Assume that a new element is inserted at the end of the linked list 􀂅

2)Upon insertion of the i-th element, the expected length of the list is (i-1)/m 􀂅

3)In case of a successful search, the expected number of elements examined is 1 more that the number of elements examined when the sought-for element was inserted!

The expected number of elements examined is thus

Calculation of expected time for successful search

Now add '1' to signify the time for computing the hash function

We get,

Final Answer

B)INTUITION For successful search you will compute hash function O(1) and traverse through half of the keys in the chain on average