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

Improve this question
$\endgroup$
2
  • 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
    Commented Nov 3, 2015 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
    Commented Nov 4, 2015 at 10:14

1 Answer 1

Reset to default
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)$.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Nov 4, 2015 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
    Commented Nov 4, 2015 at 10:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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