GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
98 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)   | 98 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.5k 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 Apr 2017
  1. akash.dinkar12

    3508 Points

  2. Divya Bharti

    2542 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Shubham Sharma 2

    1610 Points

  7. Debashish Deka

    1588 Points

  8. Arunav Khare

    1454 Points

  9. Kapil

    1424 Points

  10. Arjun

    1420 Points

Monthly Topper: Rs. 500 gift card

22,076 questions
28,040 answers
63,230 comments
24,135 users