#testseries

Question

Question No. 3
Incorrect
You: 01:38
Avg. 02:08
Marks -0.33

Consider an open-address hash table with uniform hashing. What is the time complexity for successful search?
$O\left(\alpha^{2}\right)$
$O(\alpha)$
$O(1-\alpha)$
$O(1+\alpha)$

Comments

option D

---

isn't option B and Option D are equivalent?

---

that's what my confusion is option b and d are looking equivalent

and in uniform hashing the probe sequences of each key is likely to be m! permutations .Uniform hashing generalizes to produce a whole probe sequence and in open addressing to compute the probe sequences none of the techniques (linear probing, quadratic probing , double hashing) fulfills the assumption of uniform hashing

source - cormen

then what will be its time complexity?

---

share your approach @arvin

---

i just comment about options not for answer

for answering this question, it requires what is α means and what is Hash table size and what is case(best or worst or average) information

Answer 1

here we consider UNIFORM HASHING( as given) which states that the next item to be hashed has an equal probability of being placed into any of the slots independent of any other elements.

assuming that the hash values can be calculated in T(h(x)) =O(1) and the key value to be searched has an expected length of α.

than total time will be O(1+α).