Consider the algorithm for sequential search, from below. 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.

Algorithm Search(A,n)

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

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

for i 0 to n 1 do

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

return(-1);

(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.