The Gateway to Computer Science Excellence
0 votes

in Algorithms by | 89 views
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

1 Answer

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




by Loyal

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,215 questions
60,016 answers
94,703 users