CSE 290A, Spring 2020: Lec 10, Balls and bins
C. Seshadhri · 87:10
This lecture presents the core balls-and-bins facts a randomized-algorithms student needs: collisions appear at \(m=\Theta(\sqrt{n})\) (birthday paradox), covering all \(n\) bins takes \(n Hn \approx n\log n\) tosses...