2
$\begingroup$

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.

$\endgroup$
11
  • 2
    $\begingroup$ are you familiar with the term expected value (from a probability course)? $\endgroup$
    – nir shahar
    Aug 29, 2021 at 15:36
  • 3
    $\begingroup$ Then this $\frac{1}{n}$ is there because they calculated the expected value of the number of slots we need to search. The $\frac{1}{n}$ is therefore there because we are averaging over the $n$ items. $\endgroup$
    – nir shahar
    Aug 29, 2021 at 16:06
  • 2
    $\begingroup$ Yes precisely. But the distribution is uniform so all $Pr(x_i)$ are $\frac{1}{n}$. Basically, its just a regular old average. $\endgroup$
    – nir shahar
    Aug 29, 2021 at 18:19
  • 1
    $\begingroup$ You took it outside the average: averaging a lot of $1$s will still be a $1$. Or simply, because $\frac{1}{n}\sum_{i=1}^n 1 = \frac{1}{n} n = 1$ $\endgroup$
    – nir shahar
    Sep 8, 2021 at 22:22
  • 1
    $\begingroup$ Oh, this is because you have to do at least one more operation each time after you find where it should be. Or, you can also think of it as "insurance" that we still do operations even when the list is empty. This $1$ there just means you anyways do some computation except finding whatever you wanted to $\endgroup$
    – nir shahar
    Sep 8, 2021 at 22:40

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.