Question 5543 – Data-Structures
November 23, 2023Question 630 – Computer-Networks
November 23, 2023Question 5649 – Data-Structures
Given an open address hash table with load factor α < 1, the expected number of probes in a successful search is
Correct Answer: B
Question 482 Explanation:
Analysis of Open Addressing:
→ 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.
→ 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.
→ 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.
→ 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.
At most (1/α) ln ((1–α)/α)
At most (1/α) ln (1/(1–α))
At least (1/α) ln (1/(1– α))
At least (1/α) ln (α/(1– α))
Subscribe
Login
0 Comments