2,606 views
4 votes
4 votes

Given an open address hash table with load factor $\alpha <1$, the expected number of probes in a successful search is

  1. Atmost $\frac{1}{\alpha}$ In $( \frac{1-\alpha}{\alpha})$
  2. Atmost $\frac{1}{\alpha}$ In $( \frac{1 }{1-\alpha})$
  3. Atleast $\frac{1}{\alpha}$ In $( \frac{1 }{1-\alpha})$
  4. Atleast $\frac{1}{\alpha}$ In $( \frac{\alpha }{1-\alpha})$

2 Answers

5 votes
5 votes

Option B 
 

Theorem 11.6: Given an open-address hash table with load factor α = n/m < 1, the expected number of probes in an unsuccessful search is at most 1/(1 − α), assuming uniform hashing.
Theorem 11.8: Given an open-address hash table with load factor α = n/m < 1, the expected number of probes in a successful search is at most (1/α) ln (1/(1 − α)), assuming uniform hashing and assuming that each key in the table is equally likely to be searched for.

http://www2.hawaii.edu/~nodari/teaching/f15/Notes/Topic-06.html

edited by
Answer:

Related questions

3 votes
3 votes
1 answer
2
go_editor asked Jul 14, 2016
4,038 views
A virtual memory based memory management algorithm partially swaps out a process. This is an example ofshort term schedulinglong term schedulingmedium term schedulingmutu...
2 votes
2 votes
1 answer
3
2 votes
2 votes
3 answers
4