261 views
Consider an open-address hash table with uniform hashing. Give upper bounds on the expected number of probes in an unsuccessful search and on the expected number of probes in a successful search when the load factor is $3/4$ and when it is $7/8$.

the expected number of probes in an unsuccessful search is at most 1/(1 - alpha)

also
Given an open-address hash table with load factor  < 1, the expected number of probes in a successful search is at most

$1/\alpha \ln (1/1-\alpha )+1/\alpha$

when load factor is ¾ hence for 1st case max probe is = $1/1-3/4 = 4$ for unsuccessful

and for successful = $4/3\\ln (4) + 4/3 = 3.18 approx$

calculate for 2nd part similarly

by