2
$\begingroup$

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 2

4

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

  • 0
    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.2012-09-15
0

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$

  • 0
    Well, the OP has two answers to pick from, and there are two interpretations of his post, so we have room for ambiguity!2012-09-14