Let S be an array containing unordered elements and you are to develop an algo$-$

rithm to find the location of a given x in S$.$ Measure the run$-$time in terms of the number

of comparisons required. Average case analysis should be done rigorously by computing the

average over all possible inputs, taking each input to be equally likely.