1
$\begingroup$

I'm currently reading the paper "The Power of Simple Tabulation Hashing" by Mihai Patrascu and Mikkel Thorup [1] because I want to adapt the proof of the constant time complexity of linear probing for modified tabulation hashing. I would like to ask a question about Corollary 11 (page 17). In this corollary is shown that $Pr[R \ge l] \le 2^{-\Omega(l\epsilon^2)} + (l/m)^\gamma$ for $\alpha \ge 1/2$ and $Pr[R \ge l] \le \alpha^{\Omega(l)} + (l/m)^\gamma$ for $\alpha \le 1/2$ when $\gamma = O(1)$ and $l \le n^{1/(3c)}/\alpha$. Here R is the length of the run during linear probing and $c \ge 1$.

Then as I understand, we can prove that $E[R] = O(1/\epsilon^2)$ using the formula $E[X] = \sum_{l=1}^{n} Pr[X \ge l]$. Could you please explain how do we apply the last formula if $l > n^{1/(3c)}/\alpha$? Intuitively, I understand that we have a tight concentration around $O(1/\epsilon^2)$ and, thus, the expectation is around it. But how do we take into account that $l$ can be greater than $n^{1/(3c)}/\alpha$ when showing that $E[R] = O(1/\epsilon^2)$? Moreover, what if $1/\epsilon^2 > n^{1/(3c)}/\alpha$? Then how do we prove that $E[R] = O(1/\epsilon^2)$?

Thank you very much for you help.

$\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.