I'd like to calculate the average case performance of linear search. According to wikipedia:
If the value being sought occurs once in the list, and all orderings of the list are equally likely, the expected number of comparisons is $\frac{n+1}{2}$.
However, if it is known that it occurs once, then at most $n - 1$ comparisons are needed, and the expected number of comparisons is $\frac{(n+2)(n-1)}{2n}$.
The first value is calculated as $(1 + 2 + \cdots + n)/n = (n+1)/2$ since with probability $1/n$ the marked value is the first value in the checked sequence, with probability $1/n$ the marked value is the second checked possibility, etc.
I would have thought that the second value, $\frac{(n+2)(n-1)}{2n}$, would be similarly calculated as $(1 + 2 + \cdots + n-1)/n$ but this doesn't give the correct answer. How is $\frac{(n+2)(n-1)}{2n}$ derived?
If the character is in the last or second-to-last position there are $(n-1)$ comparisons needed. Else, if it is in any other position, say position $t$, there are $t$ comparisons needed to find it. Let $E_i$ be the event the character is in position $i$. We have $P(E_i)=\dfrac{1}{n}$ for all $i$. so,
$$\begin{align*}E(I) &= \sum_{i=1}^{n-1} \dfrac{1}{n}i + \dfrac{1}{n}\cdot(n-1)\\ &= \dfrac{1}{n}\sum_{i=1}^{n-1}i + \dfrac{n-1}{n}\\ &= \dfrac{1}{n}\dfrac{(n-1)(n)}{2} + \dfrac{n-1}{n}\\ &= \dfrac{(n-1)}{2} + \dfrac{n-1}{n}\\ &= \dfrac{n(n-1) +2(n-1)}{2n}\\ &= \dfrac{(n-1)(n+2)}{2n}\end{align*}$$