search
Log In
0 votes
124 views

How to solve such kind of questions ? 

Can anybody tell what's is the concept behind this ??

 someone provide me link so that I read it and understand the actual  concept

 

in DS
recategorized by
124 views
0
5?
0
No bro it's 6
0

Yes its should be 6 i forgot about the last access..

My thought:

In load factor $\frac{n}{m}$ => I have total $'n'$ numbers inserted into a hash table which has $'m'$ slots.

So if we have to declare it as an unsuccessful probe, in the worst case scenario all the $'5'$ elements are one after the other i.e. we have to probe all those $n slots$ first where you will find all are mismatched and in the next attempt you find the blank after seeing this we say that the element is not in the hashtable  

So total will be n+1=> worst case for unsuccessful attempts.

1
0
Yes you are right $\frac{1}{1-\alpha}$ where $\alpha$ is load factor.

But the biggest worry for me how to remember these formulae :(

1 Answer

0 votes
Number of probes in unsuccessful search  = $\displaystyle \frac{1}{1-x}$
where x= load factor of hash table
since, x = $\displaystyle \frac{5}{6 }$

Therefore using above formula , x= $\displaystyle \frac{5}{6 }$ , as no. of probes in unsuccessful  search= 6.

Related questions

1 vote
0 answers
1
232 views
The keys 44, 63, 29, 78, 23, 6, 81, 14, 13, 12 and 52 are inserted into an initially empty hash table of length 12 using linear probing with hash function h(k)= k mod 12. What is the probability that the 10th slot will be filled next? i. 11/12 ii. 1 ... slot is left which have a probability of filling as 1 because no matter what index we get for the next insert we are going to fill 10th slot only.
asked Oct 31, 2018 in DS vinay chauhan 232 views
0 votes
1 answer
2
408 views
Consider the hashing table with 'm' slots and 'n' keys. If the expected number of probes in unsuccessful search is 3. The expected number of probes in a successful search is_ Answer 1.647
asked Jan 27, 2019 in DS Ram Swaroop 408 views
0 votes
0 answers
3
161 views
What is the number of collisions while doing insert operation on the hash table? Options are 3 4 5 6 Answer is 4 Can anyone tell me how? ​​
asked Nov 25, 2018 in DS Jyoti Kumari97 161 views
...