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.