Given a set of n elements the number of random samples until a collision is bounded by $\mathcal{O}(\sqrt{\pi \cdot n/2})$.
I have to give a proof using the following theorems:
- $1-x<=e^{-x}$
- $\int_{0}^{N} f(x) dx \leq\sum_{i=0}^{N}f(i)\leq\int_{0}^{N+1} f(x) dx$
- $\int_{0}^{\infty}e^{-x^2}dx=\sqrt{\pi}/2$
So I calculated
$$\begin{align} P(\text{no collision when drawing k samples}) \\ &= 1-\prod_{i=1}^{k-1}1-i/n \\\\\\ &\geq 1-\prod_{i=1}^{k-1} e^{-i/n} \end{align}$$
This is the point where I stuck.I tried using the series representation of the exponential function or adding the exponents using the sum of natural numbers but both didn't bring me further.