1
$\begingroup$

I was reading this very good summary of Cuckoo hashing.

It includes a result (page 5) that:

A stash of constant sizes reduces the probability of any failure to fall from $\Theta(1/n)$ to $\Theta(1/n^{s+1})$ for the case of $d= 2$ choices

It references the paper KMW08. But KMW08 only has the result (Theorem 2.1) that:

For every constant integer $s \geq 1$, for a sufficiently large constant $\alpha$, the size $S$ of the stash after all items have been inserted satisfies $Pr(S \geq s) =O(n^{-s})$.

Note that the $s$ in the different theorems is slightly different, in the first if the stash is of size $s$, it is not a failure, in the second, if the stash is of size $s$ it is a failure. This is why the first has $s+1$ and the second has $s$.

The difference between the two is then that the first uses theta-notation, whereas the second uses big-O notation. So my questions:

  • Do we know that the failure probability is $\Omega(n^{-(s+1)})$?
  • If so, do we know the constants in the $\Theta(n^{-(s+1)})$ expression?

And if so, which papers presented these results?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.