I am trying to prepare for an exam and I am not sure how to solve this task:
Given is a hash function with m buckets, which uses a 1-universal hash function h: U -> H and handles collisions with lists. The table was filled with n keys.
1)Specify the probability that the first bucket in the table is empty.
2) How should m be chosen as a function of n such that the expected total number of collisions is in O (1)?
My idea:
1) -probability that it lands in one bucket: 1/m
-probability that it lands in a particular bucket: 1- 1/m
-probability that after n inserts, the first bucket is empty: $(1-1/m)^n$
2) $\Omega(n^2)$
Did I do that right?