DID WE AVERAGE OVER ALL POSSIBLE INPUTS?

Let us allow the possibility that $x$ might not be in $L$.

$$\begin{eqnarray*} E_{0} = \mbox{event that $x \not\in L$} \end{eqnarray*}$$

Let

$$\begin{eqnarray*} P(x \in L) & = & q\\ P(x \not\in L) & = & 1-q = P(E_{0}) \end{eqnarray*}$$

For $k\geq 1$,

$$\begin{eqnarray*} P(E_{k}) & = &P(x \in L \mbox{and} x = L[k])\\ & = &... ...ox{given that } x \in L )\\ & = &q \frac{1}{n} = \frac{q}{n} \end{eqnarray*}$$

Thus,

$$\begin{eqnarray*} A(n) & = &\sum_{k=0}^{n} P(E_{k})t(E_{k})\\ & = &\sum_{k=1}... ...n} \frac{n(n+1)}{2} + (1-q)n\\ & = &q\frac{n+1}{2} + (1-q)n \end{eqnarray*}$$

Thus,

• if $q = 1, x \in L, A(n) = \frac{n+1}{2}$
• if $q = 0, x \not\in L, A(n) = n$
• if $q = 1/2$,
  $$\begin{eqnarray*} A(n) & = &\frac{1}{2} \frac{n+1}{2} + \frac{1}{2}n\\ & = &\frac{n+1+2n}{4}\\ & = &\frac{3n}{4} + \frac{1}{4} \end{eqnarray*}$$
  
  

Cost, Work = time complexity.