# hash-tables - Expected-time for an unsuccessful search

The following question is from MIT-OCW 6.006, Spring-2008, Problem-Set 2, Q-3.c.

Suppose you have a hash table where the load-factor $$\alpha$$ is related to the number $$n$$ of elements in the table by the following formula: $$\alpha = 1 − \frac{1}{\log n}$$ If you resolve collisions by chaining, what is the expected time for an unsuccessful search in terms of n? (assume simple uniform hashing)

My reasoning: the expected-time for an unsuccessful search would be $$\Theta(1 + E[X])$$, where $$E[X]$$ is the expected number of elements in any slot after the insertion of n-elements.

Now, by definition, we have $$\alpha = \frac{n}{m}$$, which combined with the above formula we get $$\frac{1}{m} = \frac{1}{n}\Bigl(1 - \frac{1}{\log n}\Bigr)$$. And based on simple-uniform hashing, this is the probability with which the $$(n+1)^{th}$$ element will hash to any particular slot.

Let $$X_{i}$$ be an indicator random-variable, where $$i = 1, 2, ..., n$$, which indicates that the $$i^{th}$$ element added to the hash-table (which at this piont contains $$(i-1)$$ elements) hashes to a particular slot, i.e. $$X_{i} = \begin{cases} 1, & \frac{1}{m} = \frac{1}{(i-1)}\Bigl(1 - \frac{1}{\log (i - 1)}\Bigr) \\ 0, & 1 - \frac{1}{m} \end{cases}$$ Then, the total number of elements $$X$$ in any particular slot , is given by $$X = \sum_{i=1}^{n}X_{i}$$ And the expected number of elements in any particular slot becomes: \begin{align} E[X] & = \sum_{i=1}^{n} E[X_{i}] \\ & = \sum_{i=1}^{n} \biggl\{\frac{1}{(i-1)}\Bigl(1 - \frac{1}{\log (i - 1)}\Bigr)\biggr\} \end{align}

But the $$|E[X_i]| = \infty$$, when $$i = 1, 2$$. This is where I got stuck!

So, is my reasoning correct? And if not, how to solve this problem?