GATE CSE
First time here? Checkout the FAQ!
x
+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$ ??
asked in Algorithms by Boss (8.8k points)   | 121 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 Sep 2017
  1. Habibkhan

    6970 Points

  2. Warrior

    2490 Points

  3. Arjun

    2368 Points

  4. rishu_darkshadow

    2136 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. makhdoom ghaya

    1760 Points

  8. manu00x

    1750 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,060 questions
33,668 answers
79,747 comments
31,079 users