238 views
Consider the hashing table with 'm' slots and 'n' keys. If the expected number of probes in unsuccessful search is 3. The expected number of probes in a successful search is_
in DS
edited | 238 views
+2
Expected number of probes in open addressing in case of an unsuccessful search = 1/(1-$\alpha$) , where $\alpha$ denotes the load factor i.e. n/m.

So 1/(1-$\alpha$) = 3

Hence, $\alpha$ = 2/3

Now, Expected number of probes in open addressing in case of an successful search = (1/$\alpha$)*ln(1/(1-$\alpha$))

Putting $\alpha$=2/3 in the above formula, we get the expected probes for successful search as 1.647.
0
why have you considered double hashing formula here? And why not linear probing?
0
This is the formula that is used for open addressing..
+1
+1

thanks :)

0

Now I think this question is incomplete , right @Somoshree Datta 5

0
yes..they should have mentioned which hashing to use
0

visit this link..they have given this formula for uniform probing, not double hashing..

0

http://web.ist.utl.pt/fabio.ferreira/material/asa/clrs.pdf

Visit page 210 of CLRS..here also they gave this formula for open addressing..

0

most of the questions of test series are incomplete