Question

Subject Name: Design and Analysis of Algorithm

1. An array stores 100 keys. Given that the unit cost of comparing a key with a search key is c, determine the expected cost of searching the array for the following cases:

(i)   There is equal probability of finding the search key in any of the cells.

(ii) There is 60% chance that the key is in the first 50 cells and 40% chance that the   search key is in the next 50 cells.

(iii) There is 66% chance that the key is in the array, and 44% chance that the key is not in the array.

Answer 1

Ans

i) There is equal probability of finding search key in any of the cells.

Then search begin from start till end.

Cost = c, 2c,3c,4c.,........,100c

Average cost = c+2c+.....+100c/101 = 100*101*c/2*101 = 50c

= 50c

.

.ii) 60% in first half.

Cost = 0.6(c,2c,3c,4c......50c) + 0.4(51c,52c,.....100c)

= 0.6(c*(50)(51)/2) + 0.4((100*101-50*51))/2)/101

765c+1510c /101

22.52 c

.

.

iii) 66% key is in array

for key in array average cost = 50c from i)

cost for not in array = 100c

cost = 0.66*50c + 0.34*100c

= 67c

.

If any doubt ask in the comments.

Please appreciate the work by giving a thumbs up.