The Gateway to Computer Science Excellence
0 votes
80 views

Im getting 1,8 is anyone getting 1,9????

 

in Algorithms by (177 points)
edited by | 80 views
0
question?
0
see the pic carefully
0
no pics @nag.swarna
0

This

0
i m getting 1,9

what is answer?
0
1,9 is the answer

Can u please provide the solution
+2
Yes I'm getting 1,9
Worst case occurs require N+1 comparision to know the element is not there in the hash table where N is the size of the largest cluster.
Here N is formed of index(7,8,9,10,11,12,0,1)
0
Thank U
0

arrange in the bucket using h(k)

 0  38 
 1  14
 2  -
 3  42 
 4  -
 5 70
 6 -
 7 7
 8  8
 9  21
 10  34
 11  11
 12  25

check for any x that is not present in bucket.

search for x%13=2 or 4 or 6 ==> blank found

so, 1 key comparison. Minimum=1

---------------------------------------------------------------

search for x%13=7 (say, x=20)

not found untill it reaches linearly till key 2. blank found. so, total (8+1)= 9 key comparison.

maximum=9

1 Answer

+1 vote
0 38
1 14
2  
3 42
4  
5 70
6  
7 7
8 8
9 21
10 34
11 11
12 25

This will be the distribution of the Hash Table after all the  keys has been inserted in the table.

Minimum no. of key comparison is 1. This happens when either at the location[ key%13 ] key is present or when at the location[ key%13 ] no key is present.

For Maximum Key Comparison consider the largest cluster in the given hash table. The largest cluster in given case consist of location no. {7,8,9,10,11,12,0,1}. The size of largest cluster being 8.

Now suppose you are searching for the key value 72.

Hash Value = 72%13 = 7.

Now the search process will look as of like this.

First value at location[7] will be compared with 72, since 7!=72( No. of comparisons = 1). Since collision resolution technique used is linear probing. Next ,

location[8] will be compared with 72, since 8!=72( No. of comparisons = 2). Since collision resolution technique used is linear probing. Next ,

location[9] will be compared with 72, since 21!=72( No. of comparisons = 3). Since collision resolution technique used is linear probing. Next ,

...

...

...

location[1] will be compared with 72, since 14!=72( No. of comparisons = 8). Since collision resolution technique used is linear probing. Next ,

location[2] will be compared with 72, since null!=72( No. of comparisons = 9).

Since, there is no key present at this location the search process will stop and null (Key not Found) will be returned.

Last comparisons is very important. This is also required along with all the remaining 8 comparisons to stop the algorithm.

 

by Junior (815 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,644 questions
56,505 answers
195,555 comments
101,049 users