# Separate Chaining hashing: time complexity of successful search

In a simple uniform hashing with chaining collision, the time complexity of a successful search is: $$Θ(1 + (1 + \frac{α}{2} - \frac{α}{2n}))$$ where $$α=\frac{n}{m}$$, but I don't understand how to determine it.

I tried to calculate the cost of access of each node in the list and to divide it by the number of elements of the list, but it doesn't seem correct. $$1+\frac{m}{n}\cdot \sum _{i=0}^{\frac{n}{m}}\frac{n}{m}-i=1+\frac{n+m}{2m}$$

The expected length of a chain when the $$i$$th element is added is $$\frac{i-1}m$$. So if we mentally re-order the elements in the hash map to be in order of insertion, we can calculate the expected length of a chain $$E[l]$$ when performing a search with $$n$$ elements in the map:
\begin{align} E[l]&=\frac{1}{n}\sum_{i=1}^n \frac{i-1}m = \frac{1}{nm}\left(-n + \sum_{i=1}^n i\right) = \frac{1}{nm}\left(-n + \frac{1}{2}n(n+1)\right)\\ E[l] &= \frac{1}{m}\left(-1 + \frac{1}{2}n+\frac{1}{2}\right) = \frac{n}{2m} - \frac{1}{2m} \end{align}
Now you can substitute $$\alpha = \frac n m$$ and find $$E[l] = \frac \alpha 2 - \frac{\alpha}{2n}$$.
• Is it not clear to me why the element is in position $\frac{i-1}{m}$? What I mean is that, if a list is long $\frac{6}{2}\;(m=6, n=2)$, the element shouldn't be in the position $1, 2, 3$ of the first or second list (therefore in the $\frac{n}{m}-i$ position)? Apr 24 '20 at 7:59
• @Shyvert $\frac{i-1}m$ isn't a position, it's an expected chain length. When inserting the $i$th element there are already $i-1$ elements in the hash map, and we assume that these are uniformly distributed. Therefore we expect each cell of the hash map to have $\frac{i-1}{m}$ elements already.