# Prove inequality with $\theta$

I was given a task about hash tables, to prove that for a hash table with n buckets and separate chaining collision resolution the probability of collision occurrence within $$\theta(\sqrt{n})$$ inserts is more that $$\frac{1}{2}$$.

From basic probability theory I've come to the following inequality describing probability of collision occurrence within $$j$$ inserts: $$1\cdot\Big(1-\frac{1}{n}\Big)\cdot\Big(1-\frac{2}{n}\Big)\cdot ... \cdot \Big(1-\frac{j-2}{n}\Big)\cdot\Big(1-\frac{j-1}{n}\Big) \geq \frac{1}{2},\ for\ j=\theta(\sqrt{n})$$ But I've been struggling a lot with this and unable to solve it. Do you have any ideas? Have been thinking about plots and exponent, unfortunately with no result

• Looks like exponent may be a real deal here.. Apr 18 '20 at 11:43

Hint: Try to use following assumption from Taylor's series expansion: $$e^x \geq x+1$$.