+1 vote
121 views
How do i prove that : : : In hashing n items into a hash table with k locations, the expected number of collisions is $n - k + k( 1-\frac{1}{k})^n$ ??
u can take a manual example of "k " and "n" and perform the algo.. u will get it
I  don't understand.

We have n items to insert and size of hash table of is K .

so the probability A location is empty after first insertion =  (1-probabilty of filling that location)=(1-(1/k))

so probability of A location is empty after n insertion = (1-(1/k))^n

Possible no of empty location  = k*(1-(1/k))^n

Expected No of collision = n - occupied location

= n - (total location - empty location)

= n- (k - k*(1-1/k)^n)

=n- k + k*(1-1/k)^n
@correct
Can you tell me when to use this

expected number of collision = n(n-1)/2m
How is it true:

"Expected No of collision = n - occupied location"

Please explain how to understand this.

Should it not be "Expected No of collision = n - insertions into previously empty positions"?