4
$\begingroup$

My question is related to this: Hash-Table in Practice


In [1] page 7, it is said that if we throw $n$ balls into $k$ bins, then each bin contains at most $\frac{n}{k}+O(\sqrt[2]{(\frac{n}{k})\log k}+\log k)$ elements with a high probability.

Question 1: Why is $O()$ used in the above estimation?

Question 2: Does it mean the probability that a bin contains more than the above value is negligible?


[1]. http://www.pinkas.net/PAPERS/FNP04.pdf

$\endgroup$
  • 1
    $\begingroup$ 1) Since your two questions are unrelated, please ask them separately. 2) Is your real question either one of "what does $O$ mean" or "what does 'high probability' mean"? $\endgroup$ – Raphael Nov 3 '15 at 18:13
  • $\begingroup$ @Raphael First off, thank you for the editing. I have add some comments on the answer. Could you please give your idea about that. Thanks. $\endgroup$ – user153465 Nov 4 '15 at 10:14
3
$\begingroup$

A more formal statement of the claim is as follows. There is a constant $C > 0$ and for each $k$, a function $\epsilon(n)$ satisfying $\lim_{n\to\infty} \epsilon(n) = 0$, such that if you throw $n$ balls into $k$ bins, then with probability at least $1-\epsilon(n)$ the contents of each bin is at most $ \frac{n}{k} + C(\sqrt{(\frac{n}{k})\log k}+\log k)$.

$\endgroup$
  • $\begingroup$ Thank you very much for the answer. To make it more clear to me, could you please give me a concrete example; for instance, if $n=10^4$ and $k=10$ then what the probability and max load would be? I do not understand how $C$ and the probability are related; in other words, how we can set $C$ to ensure overflow would not happen with a high probability (or "overwhelming" probability). $\endgroup$ – user153465 Nov 4 '15 at 10:09
  • 1
    $\begingroup$ You don't get to set $C$ or $\epsilon(n)$. They are given to you by the proof. If you want to know concrete values, you can look at the proof and extract these quantities. You may find out that for any $C > 0$ you can find an appropriate $\epsilon(n)$; or you may find out that the proof only works for certain values of $C$. The only way to know is to look at the proof. $\endgroup$ – Yuval Filmus Nov 4 '15 at 10:20

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.