Algorithms question Already have the minimum and maximum number of probes, so pl

Question

Algorithms question

Already have the minimum and maximum number of probes, so please don't answer above!! The actual question is...

Which of the following scenarios lead to expected liner running time for a random search miss in a linear probing hash table?

a. All keys hash to the same index.

b. All keys hash to different indices.

c. All keys hash to an even-numbered index

d. All keys hash to different even numbered indeces.

.4.12 Suppose that the keys A through G, with the hash values given below, are inserted in some order into an initially empty table of size 7 using a linear-probing table (with no resizing for this problem). Which of the following could not possibly result from inserting these keys? a. E F G A C B D b, C E B G FDA d. C G BA D E F e. F G BD A C E build a table of size 7 with these keys, and an insertion order that justifies your answer.

Explanation / Answer

Answer is as follows :

Correct Option is a i.e. All Keys hash to the same Index.

Explanation :

If all keys hash to the same location then the i-th inserted key would need i lookups to be found. The probability of looking up i-th key is 1/n (since it’s random). If you know some probability it’s trivial to show that such lookups have linear time.

So the correct Option is A.

if there is any query please ask in comments..

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.