Calculating Average Case Complexity I am trying to find the average case complexity of a sequential search. I know that the value is calculated as follows: 
Probability of the last element is $\frac{1}{2}$
Probability of the next to last is $\frac{1}{4}$
Probability of any other elements is $\frac{1}{4n-8}$
I can assume the I have a list of n $\geq$ 3. How Would I go about solving this? 
 A: Let $X \in \{1,2,\dots,n\}$ be the position of the element you're searching for. This random variable has the following probability mass function
$$p_X (k) = \left\{\begin{array}{cl} \frac{1}{4 n - 8} & \textrm{if} \quad{} k \in \{1,2,\dots,n-2\}\\ \frac{1}{4} & \textrm{if} \quad{} k = n-1\\ \frac{1}{2} & \textrm{if} \quad{} k = n\end{array}\right.$$
where $n \geq 3$ is the size of the list / array over which you're searching. Note that
$$\displaystyle\sum_{k=1}^{n-2} p_X (k) = \frac{n-2}{4 n - 8} = \frac{1}{4}$$
and therefore 
$$\displaystyle\sum_{k=1}^{n} p_X (k) = \frac{1}{4} + \frac{1}{4} + \frac{1}{2} = 1$$
as it should be. The average case complexity is given by the expected value of $X$, which is
$$\mathbb{E} (X) = \displaystyle\sum_{k=1}^{n} k \, p_X (k) = \left[\frac{1}{4 n - 8}\displaystyle\sum_{k=1}^{n-2} k \right] + \frac{n-1}{4} + \frac{n}{2} = \frac{7 n - 3}{8}$$
A: You have $\frac 12$ chance of finding it the first try, $\frac 14$ of needing two, then $\frac 1{4n-8}$ of using any number from three to $n$. The expectation is then $\frac 12 \cdot 1+\frac 14\cdot 2+\frac 1{4n-8}\sum_{i=3}^n i$
