# Balanced allocation-Hash table- overflow probability

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

In  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{(\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"? – Raphael Nov 3 '15 at 18:13
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). – user153465 Nov 4 '15 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. – Yuval Filmus Nov 4 '15 at 10:20