GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
88 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$ ??
asked in Algorithms by Boss (8.6k points)   | 88 views
u can take a manual example of "k " and "n" and perform the algo.. u will get it
I  don't understand.
Please provide a manual example

1 Answer

+3 votes
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
answered by Loyal (3.4k points)  
@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"?
Top Users Feb 2017
  1. Arjun

    4704 Points

  2. Bikram

    4004 Points

  3. Habibkhan

    3738 Points

  4. Aboveallplayer

    2966 Points

  5. sriv_shubham

    2278 Points

  6. Smriti012

    2212 Points

  7. Arnabi

    1814 Points

  8. Debashish Deka

    1788 Points

  9. sh!va

    1444 Points

  10. mcjoshi

    1444 Points

Monthly Topper: Rs. 500 gift card

20,788 questions
25,938 answers
59,535 comments
21,929 users