Timeline for Balanced allocation-Hash table- overflow probability
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 4, 2015 at 10:20 | comment | added | Yuval Filmus | 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. | |
| Nov 4, 2015 at 10:09 | comment | added | user153465 | 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). | |
| Nov 4, 2015 at 9:57 | vote | accept | user153465 | ||
| Nov 3, 2015 at 18:25 | history | answered | Yuval Filmus | CC BY-SA 3.0 |