# Balanced allocation-Hash table- overflow probability

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) 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"? Commented Nov 3, 2015 at 18:13
• @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. Commented Nov 4, 2015 at 10:14

## 1 Answer

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)$.

• 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). Commented Nov 4, 2015 at 10:09
• 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. Commented Nov 4, 2015 at 10:20