# 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?

-

## 2 Answers

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$

-
Haven't you reversed the list? Or, haven't you started the search from the end of the list? – Rod Carvalho Sep 14 '12 at 22:56
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
The problem with your approach is that it would be wise to separate the implementation from the data. Or, to put it more precisely, the implementation of the search algorithm should not be optimized for one single instance of the problem. – Rod Carvalho Sep 14 '12 at 23:15
@Rod: I actually read "last" as most recent and thought of it as caching – Ross Millikan Sep 14 '12 at 23:27
Well, the OP has two answers to pick from, and there are two interpretations of his post, so we have room for ambiguity! – Rod Carvalho Sep 14 '12 at 23:29