Prove that the probability that an insertion into a cuckoo hash table probes $t$ array locations is $O(\frac{1}{2^{t/2}})$. Keep in mind that there are two tables, each with size $s \ge 2n$, where $n$ is the number of elements in the set.

I'm trying to use induction, but I don't know if this is the best method to go about proving this.

The worst case to probe $1$ array location would be when all $n$ element are stored in the first table, and we get probability $\frac{n}{2n} = \frac{1}{2} = O(\frac{1}{\sqrt{2}})$ for insertion.

The worst case to probe $2$ array locations would be when all $n$ elements are stored in the first table, we hit the first table, and we succeed in the second table. This has the same probability as it does to probe $1$ array location.

However, I don't know how to continue the analysis. For example, what's the worst case probability to probe $4$ array locations? The question statement implies that the worst case is $O(\frac{1}4)$, but how do we achieve this result? If the first and second tables each have $\frac{1}4$ of their array locations occupied, then the worst case to probe $4$ elements would be hitting in the first table, hitting in the second table, hitting in the first table again, then finally inserting into the second table $\Rightarrow \frac{1}4\cdot\frac{1}4\cdot\frac{1}{4}\cdot\frac{3}4 = \frac{3}{256} \not = \frac{1}4$.

Does anyone have a clearer way of thinking about this problem?


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.