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.



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.