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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,654 questions

56,166 answers

193,872 comments

94,261 users