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
    Haven't you reversed the list? Or, haven't you started the search from the end of the list?2012-09-14
  • 0
    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}$2012-09-14
  • 0
    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.2012-09-14
  • 0
    @Rod: I actually read "last" as most recent and thought of it as caching2012-09-14
  • 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