AVERAGE-CASE COST?

• Let $x \in L$
• Further, let $x$ is equally likely to be in any position 1 through $n$.
• $E_{k}$: event that $x = L[k]$
• Probability of $E_k$ happening
  $$\begin{eqnarray*} P(E_{k}) & = &1/n, 1 \leq k \leq n\\ t(E_{k}) & = &\mbox{cost or time when $L[k] = x$}\\ & = &k \end{eqnarray*}$$
  
  
  Thus, average cost
  $$\begin{eqnarray*} A(n) &= &P(E_{1})t(E_{1})+P(E_{2})t(E_{2})+ \ldots +P(E_{n})t... ...\frac{1}{n}\left (\frac{n(n+1)}{2}\right)\\ &=& \frac{n+1}{2} \end{eqnarray*}$$