Occupancy Problem Theorem: m balls into n bins: If m=n,the max load is O( In In n/ with high probability When m (n logn),the max load is O() with high probability balls =100,bins =100 balls =2000,bins =100 6 20 dhher iwbyw 0 20 40 60 80 100 20 40 60 80 100 balls =600,bins =100 balls =5000,bins =100 20 100 10 bar bbb solthruw 0 20 40 60 80 100 20 40 60 80 100Theorem: If m = n, the max load is O ￾ ln n ln ln n ⇥ with high probability. When m = ￾(n log n), the max load is O( m n ) with high probability Occupancy Problem m balls into n bins: