option D

The Gateway to Computer Science Excellence

0 votes

0

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?

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?

+1 vote

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+**α).**

52,215 questions

60,016 answers

201,243 comments

94,703 users