Consider the linear search algorithm with scans through an


Algorithm:  Consider the linear search algorithm with scans through an n-element array a to determine if element xis in a. We say that the algorithm require i steps if x is located at index i; i.e. a[i] = x, for i = 0, 1, . . . , n ?

1. Furthermore, the algorithm requires n steps if x is not found in a.

Assume 60% of all searches fail to locate the element x in a. Moreover, for the other 40% of searches, when x is found in a, it is equally likely to be in any of the array locations.

Let S denote the number of steps needed for a linear search over an array of size n, use the above facts to find i) the domain of S, ii) a probability distribution for the domain of S, and iii) E[S].             

Please show me all the working and provide the answer.             

 

Request for Solution File

Ask an Expert for Answer!!
Data Structure & Algorithms: Consider the linear search algorithm with scans through an
Reference No:- TGS0957032

Expected delivery within 24 Hours