910 views

If $h$ is chosen from a universal collection of hash functions and is used to hash $n$ keys into a table of size $m$, where $n \leq m$, the expected number of collisions involving a particular key $K$ is

1. Less than $1$
2. Less than $lg n$
3. Greater than $1$
4. Greater than $lg n$
in DS
recategorized | 910 views

+1 vote

This is a theorem in Universal Hashing -

"If h is chosen from a universal collection of hash functions and is used to hash n keys into a table of size m, where n<=m, the expected number of collisions involving a particular key x is less than 1."

Hence ans is A

by Loyal (7.2k points)
n - m(1-(m-1)/m)^n)

For a slot collision doesn't occur given by following probability ..

1-((m-1)/m)^n

Expectation for m slot collision doesn't occur...

m((1-((m-1)/m)^n -------------- equation A

So for n keys expected number of times collision occur is ...

n - equation A

Take n= 32 and m=32 it will gives 11.58

So ans should be D.
by Boss (25.5k points)
0

what does lgn mean in option D ? is it log n ?

0
Yup
0

Don't you think most of the time option D and C will give you the same answer . one is contained in another .

for example option D says greater then logn lets consider this log2base 2 =1  means greater then 1  and option C says the same thing greater then 1.

0
Can you explain ??