An asymptotically optimal algorithm for generating bin cardinalities

Luc Devroye, Dimitrios Los

In the balls-into-bins setting, $n$ balls are thrown uniformly at random into $n$ bins. The naïve way to generate the final load vector takes $\Theta (n)$ time. However, it is well-known…