Question

Given a hash table with n keys and m slots, with the simple uniform hashing assumption (each key is equally likely to be hashed into each slot). Collisions are resolved by chaining.

(a) What is the probability that the first slot ends up empty?

(b) What is the expected number of slots that end up not being empty?

Comments

A )   (1-1/m) * (1-1/m) ...........n times     = (1-1/m)^n

---

B )   Expected number is =  m * (1- (1-1/m)^n)

---

why we are multiplying n times?

---

plz explain q b)

Answer 1

A) What is the probability that the first slot ends up empty?

ans:-       => 1 -(probability of filled up first slot)

              $  => 1 - (1/m)$

for n element  :-      $[1-(1/m)] ^ n$

B) What is the expected number of slots that end up not being empty?

ans:- suppose expected number of slots are L

then, 

Probability to fill 1 slots = $[ 1- (1/m) ] ^ n$ 

               for L slot    =>   $L* [  { 1-(1/m) }^n ]$

 

Comments

For part B, that is the expected number of slots that end up being empty. Here it is asked non-empty.

Answer 2

how u calculated expected number

Comments

just calculated expected no for 1 slot and multiply by total slots.