Question

Question:Suppose the probability that \(x\) is the \(i\) element in a list of \(n\) distinct integers is \(i/(n(n + 1))\). Find the average number of comparisons used by the linear search algorithm to find \(x\) or to determine that it is not in the list.

Short answer

Answer

The average number of comparisons used by the linear search algorithm to find or to determine that it is not in the list is \(\frac{{10n + 11}}{6}\).

Step-by-step solution

In the problem given  

\(P\)(\(x\) is the \({i^{{\rm{th }}}}\)element in a list of \(n\) distinct integers) \( = \frac{i}{{n(n + 1)}}\)

The definition and the formula for the given problem

Linear search is a very simple search algorithm. In this type of search, a sequential search is made over all items one by one. Every item is checked and if a match is found then that particular item is returned, otherwise the search continues till the end of the data collection.

Concept used:

\(\begin{aligned}{c}\sum\limits_{i = 1}^i i = \frac{{n(n + 1)}}{2}\\\sum\limits_{i = 1}^i {{i^2}} = \frac{{n(n + 1)(2n + 1)}}{6}\end{aligned}\)

Determining the sum in expanded form

The probability that the item is in the list is.

\(\begin{aligned}{c}\sum\limits_{i = 1}^n {\frac{i}{{n(n + 1)}}} &= \frac{1}{{n(n + 1)}}\sum\limits_{i = 1}^n i \\ &= \frac{1}{{n(n + 1)}} \times \frac{{n(n + 1)}}{2}\\ &= \frac{1}{2}\end{aligned}\)

Therefore, the probability that the item is not in the list is also \(\frac{1}{2}\).

If the item is not in the list then the number of comparisons are \(2n + 2\).

Similarly, if the item is the \({i^{{\rm{th }}}}\) item in the list then the numbers of comparisons needed are \(2i + 1\)

The expected numbers of comparisons are given by

\(\begin{aligned}{c} &= \frac{1}{2}(2n + 2) + \sum\limits_{i = 1}^n {\frac{i}{{n(n + 1)}}} (2i + 1)\\ &= (n + 1) + \frac{2}{{n(n + 1)}}\sum\limits_{i = 1}^n {{i^2}} + \frac{1}{{n(n + 1)}}\sum\limits_{i = 1}^n i \\ &= n + 1 + \frac{2}{{n(n + 1)}} \times \frac{{n(n + 1)(2n + 1)}}{6} + \frac{1}{{n(n + 1)}}\frac{{n(n + 1)}}{2}\\ &= (n + 1) + \frac{{2n + 1}}{3} + \frac{1}{2}\\ &= \frac{{6(n + 1) + 2(2n + 1) + 3}}{6}\\ &= \frac{{10n + 11}}{6}\end{aligned}\)

Therefore, the expected numbers of comparisons are \(\frac{{10n + 11}}{6}\).