Let us assume that we are given a real number $x$ and a list of $n$ distinct real numbers. The linear search algorithm, described below,

   linearsearch(x, a1,a2,...an):
        
        i:=1
        while(i<=n and x not equal to ai):
              i:=i+1
        if i<=n:
             loc:=i
        else:
             loc:=0

locates $x$ by successively comparing it to each element in the list, terminating when $x$ is located or when all the elements have been examined and it has been determined that $x$ is not in the list.

What is the average-case computational complexity of the linear search algorithm if the probability that $x$ is in the list is $p$ and it is equally likely that $x$ is any of the $n$ elements in the list? (There are $n + 1$ possible types of input: one type for each of the $n$ numbers in the list and a last type for numbers not in the list, which we treat as a single input.)

Now $i$ comparisons are used if $x$ equals the $i$ th element of the list and, there are $n$ comparisons are used if x is not in the list. The probability that $x$ equals $a_i$ , the $i$ th element in the list, is $\frac{p}{n}$, and the probability that $x$ is not in the list is $q = 1 − p$.

It follows that the average-case computational complexity of the linear search algorithm is

$E= \frac{p}{n} + \frac{2p}{n} +···+ \frac{np}{n} + nq$

$= \frac{p}{n}(1+2+···+n) + nq$

$= \frac{p}{n}.\frac{n(n+1)}{2}+nq$

$= p.\frac{n+1}{2}+nq$

Now if we plug in the probability that

$p = \frac{n}{n+1}$ and hence $q=\frac{1}{n+1}$ then

$E = \frac{n}{n+1}\frac{n+1}{2}+n.\frac{1}{n+1} = \frac{n}{2}+ \frac{n}{n+1} = \frac{n^{2}+3n}{2n+2}$

Now again if we plug in,

$p=1$ and hence $q=0$ then we have,

$= 1.\frac{n+1}{2}+n.0 = \frac{n+1}{2} $

Let us assume that we are given a real number $x$ and a list of $n$ distinct real numbers. The linear search algorithm, described below,

   linearsearch(x, a1,a2,...an):
        
        i:=1
        while(i<=n and x not equal to ai):
              i:=i+1
        if i<=n:
             loc:=i
        else:
             loc:=0

locates $x$ by successively comparing it to each element in the list, terminating when $x$ is located or when all the elements have been examined and it has been determined that $x$ is not in the list.

What is the average-case computational complexity of the linear search algorithm if the probability that $x$ is in the list is $p$ and it is equally likely that $x$ is any of the $n$ elements in the list? (There are $n + 1$ possible types of input: one type for each of the $n$ numbers in the list and a last type for numbers not in the list, which we treat as a single input.)

Now $i$ comparisons are used if $x$ equals the $i$ th element of the list and, there are $n$ comparisons are used if x is not in the list. The probability that $x$ equals $a_i$ , the $i$ th element in the list, is $\frac{p}{n}$, and the probability that $x$ is not in the list is $q = 1 − p$.

It follows that the average-case computational complexity of the linear search algorithm is

$$E= \frac{p}{n} + \frac{2p}{n} +···+ \frac{np}{n} + nq$$

$$= \frac{p}{n}(1+2+···+n) + nq$$

$$= \frac{p}{n}.\frac{n(n+1)}{2}+nq$$

$$= p.\frac{n+1}{2}+nq$$

Now if we plug in the probability that

$$p = \frac{n}{n+1}$$ and hence $$q=\frac{1}{n+1}$$ then

$$E = \frac{n}{n+1}\frac{n+1}{2}+n.\frac{1}{n+1} = \frac{n}{2}+ \frac{n}{n+1} = \frac{n^{2}+3n}{2n+2}$$

Now again if we plug in,

$$p=1$$ and hence $$q=0$$ then we have,

$$E= 1.\frac{n+1}{2}+n.0 = \frac{n+1}{2} $$