Question: Consider linear search. How many elements of the input sequence 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 do I solve this? Do I need to take the case where the element is not present in the sequence? For that case all the n elements needs to be checked.
Total no. of cases is (n + 1). Therefore average no. of elements to be checked = (1 + ... + n + n) / (n + 1). Is this answer correct?
Distinguishing the two cases where the element is in the array (successful search) and where it is not (unsuccessful search).
For a successful search the average is (1 + 2 + ... + n) / n = (n + 1) / 2.
For an unsuccessful search the average is just n.
The total average depends now on the mix of successful vs unsuccessful searches. For example if most of the searches are unsuccessful it will be close to n. If all searches are successful (this seems to be what is meant by the question) the average is (n + 1) / 2.
If the probability of a successful search is p, and therefore for an unsuccessful search 1-p, we get an average of p * (n+1) / 2 + (1-p) * n.