1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Looks like exponent may be a real deal here.. $\endgroup$ Apr 18 '20 at 11:43
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Will try that, look like it leads me to rather easy progression and inequality. Thanks! $\endgroup$ Apr 18 '20 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.