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?

-

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}$$

-
That was a good answer and very easy to follow. I feel that I can now solve a case complexity problem for a series that has several conditions. Basically it is a matter of defining the problem space. Matching conditions and then making a final deductive step. –  Michael Guantonio Sep 15 '12 at 0:49
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$
I assumed we were smart enough to try the most likely first. If not, it becomes $\frac n2+\frac {n-1}4+\ sum_{I=1}^{n-2}\frac I{4n-8}$ –  Ross Millikan Sep 14 '12 at 23:03