Probability of probing $t$ locations in a Cuckoo hash is $O(\frac{1}{2^{t/2}})$ locations in the worst case
Basically, you just write down everything that is necessary to have $t$ evictions and then use the universality of your hash functions to bound the probability.

Assume you want to insert $x$ and your hash functions are $f,g$. Then if you have $t$ probes if $f(x)$ is occupied that is 
$$
\begin{align}
\mathbb{P}[t=1]&amp; =\sum_{y \neq x} \mathbb{P}[f(x)=f(y)]\\
&amp;\le n \cdot 1/s \le 1/2.
\end{align}$$
since your hash function are $(1,k)$-universal (I assume).

Now for $t=2$, the place of $f(x)$ have to be occupied by some element $y$ (that is $f(x)=f(y)$), and the alternative for $y$ is blocked by some other element $z$ (that is $g(y)=g(z)$). Summing up over all possible values for $y$ and $z$ gives 
$$
\begin{align}
\mathbb{P}[t=2]&amp; =\sum_{y,z \neq x} \mathbb{P}[f(x)=f(y) \text { and } g(y)=g(z) ]]\\
&amp;\le n^2 \cdot 1/s^2 \le 1/4. 
\end{align}$$

The summands of the sum are bounded by $1/s^2$ due to the universality of the hash functions, and you have less than $n^2$ summands. 

I think from here you can continue by yourself.