# algorithms – A successful search takes \$Theta(1 + alpha)\$ time on average when resolving collisions by chaining

I would to discuss a proof found in CLRS book please.

Theorem: In a hash table in which collisions are resolved by chaining, a successful search takes time $$Theta(1 + alpha)$$, on the average, under the assumption of simple uniform hashing.

Proof: Assume we $$n$$ elements are equally likely to be searched in the table. The number of elements examined during a successful search for an element $$x$$ is 1 more than the number of elements that appear before $$x$$ in $$x$$’s list. New element will be added at the end of the list.

To find the expected number of elements examined, we take the average, over the n elements $$x$$ in the table, of 1 plus the expected number of elements added to $$x$$’s list after x was added to the list. Let $$x_i$$ denote the ith element inserted into the table, for $$i = 1, 2, cdots, n$$ and let $$k_i = key(x_i)$$. For keys $$k_i$$ and $$k_j$$, we define the indicator random variable $$X_{ij} = I {h(k_i) = h(k_j)}$$. Under the assumption of simple uniform hashing, we have $$Pr{h(k_i) = h(k_j)} = 1/m$$, $$E (X_{ij}) = 1/m$$. Thus, the expected number of elements examined in a successful search is

$$begin{gather} Eleft( frac{1}{n} sum_{i=1}^{n} left( 1 + sum_{i=1}^{n} X_{ij} right)right) tag{1} label{1}\ =frac{1}{n} times left(sum_{i=1}^{n} left( 1 + sum_{i=1}^{n} Eleft(X_{ij}right) right)right) &text{(Based on Linearlity of Expectation)}\ vdots \ =Theta(1+alpha) end{gather}$$

Problems:

1. The number of elements examined during a successful search for an element $$x$$ is 1 more than the number of elements that appear before $$x$$ in $$x$$’s list. So, if our table is empty and we have only 1 element, then the time needed would be $$O(1)$$. If all elements are hashed to first entry of the table, then we would need $$O(Elements)$$ to find the item as I understand. Why the time needed is $$Theta(1+alpha)$$ please?
2. How equation ref{1} was brought in first place? From what I understood, since all elements to be found are equally likely, then we would have $$frac{1}{n}$$, so probably this is why its their in ref{1}.
Posted on Categories Articles