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

The Gateway to Computer Science Excellence

0 votes

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

- Less than $1$
- Less than $lg n$
- Greater than $1$
- Greater than $lg n$

+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."

ref: https://gateoverflow.in/45237/hashing

Hence ans is A

0 votes

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.

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.

52,315 questions

60,433 answers

201,778 comments

95,257 users