Suppose the probability that x is the ith element in a list of n distinct integers is i/[n(n + 1)]. Find the average number of comparisons used by the linear search algorithm to find x or to determine that it is not in the list.

Expected number of comparisons = sum((number of comparison till i^{th} entry) * probability of getting the number at i^{th} entry) + n. probability that $x$ is not in the list.

Probability that $x$ is in the list = $\sum_{i=1}^n \frac{ i} {n.(n+1)} = \frac{1}{2}$

So, probability of $x$ not in the list $= \frac{1}{2}$

Now, there is a catch here. We have counted one comparison for one element in the linear list. But if we count the loop exit condition and the final found or not check also as in the algorithm give here http://www.programmingsimplified.com/c/source-code/c-program-linear-search, we get $2i + 1$ comparisons for a successful check at $i^{th}$ position and $2n+2$ comparisons if $x$ is not in the list. This would give

After comparing all elements of the list with x, we can say that x is not in the list. In this process, we performed n number of comparisons. That is why 'n' is multiplied when x is not in the list