# algorithms – Proving that a successful search of hash function is \$Theta(1+alpha)\$

Question: Prove that successful search of hash function with chaining (list at each slot) takes $$Theta(1+alpha)$$.

Given a dictionary or hash table that has a chain at each slot in case we have a collision. So, given that the load factor of table $$alpha = frac{n}{m}$$, where $$n$$ is the number of elements in the hash table and $$m$$ is the number of slots. We can see that successfully searching for item takes $$Theta(1+alpha)$$.

Solution: The answer I got did the following (Courtesy to Introduction to Algorithms book):

The expected number of elements examined during a successful search is $$1$$ more than the number of elements examined when the sought for element was inserted (since every new element goes at the end of the list). To find the expected number of elements examined, we therefore take the average, over the $$n$$ items in the table, of $$1$$ plus the expected length of the list to which the $$i$$th element is added. The expected length of that list is $$frac{i-1}{m}$$, and so the expected number of elements examined in a successful search is

$$frac{1}{n}sum_{i=1}^{n}(1+frac{i-1}{m}) = 1 + frac{1}{nm}sum_{i=1}^{n}(i-1)$$

$$…$$

Problem: how we got $$frac{1}{n}$$ in front of the sum please in $$frac{1}{n}sum_{i=1}^{n}(1+frac{i-1}{m})$$? This is my problem not the solution of the question.