Consider linear search again $($see Exercise $2\mathrm{.}1-4).$ How many elements of

the input array need to be checked on the average, assuming that the

element being searched for is equally likely to be any element in the

array? How about in the worst case? Using $-$notation, give the average$-$

case and worst$-$case running times of linear search. Justify your answers.