Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

# DSA - Graphs and Hashing -Q7

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177
+1 vote

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

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

$(D)m{\begin{pmatrix} \frac{1}{m} \end{pmatrix}}^n$

reshown Aug 6, 2020

Probability of some slot to end up Empty : $\left ( \frac{m-1}{m} \right )^n$

Probability of some slot to end up Not Empty : $1 - \left ( \frac{m-1}{m} \right )^n$

Total slots = m

the expected number of slots that end up Not being empty  :

$m \left [ 1 - \left ( \frac{m-1}{m} \right )^n \right ]$

https://gateoverflow.in/115354/given-hash-table-with-slots-simple-uniform-hashing-assumption

answered Aug 14, 2020 by (226,240 points)
sir why D option is not correct