The Gateway to Computer Science Excellence
0 votes
75 views

in Algorithms by (299 points) | 75 views
0
option D
0
isn't option B and Option D are equivalent?
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?
0
share your approach @arvin
0
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 Boss (12k points)

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
50,654 questions
56,166 answers
193,872 comments
94,261 users