Consider the algorithm for sequential search:

Algorithm Search(A,n)

Input: An array A[n], where n1; an item x

Output:Index where x occurs in A, or -1

for i0 to n1 do

if A[i] = x then return(i);

return(-1);

In each part of this question we make an assumption about the probability distribution of the presence and location of x in the array. For each part, compute the expected number of times the comparison if A[i] = x. . . is executed if the given assumptions hold.

(a) The item x is in the array. It is equally likely to be in any of the n locations in the array.

(b) The probability that x is in the array is 0.5. If it is in the array, it is equally likely to be in any of the n locations in the array.