# Average-case complexity of linear search where half of the elements in the array are duplicates

I know that for an array of size n distinct elements, the Average Case complexity for linear search is as follows:

A(n) = $\frac{n + 1}{2}$

However, I am having trouble coming up with the Average Case complexity in the case where half of the elements in the size n array are duplicates. Take, for example, this array of integers:

1 2 6 6 5 4 6 6 6 3

Here is my thought-process so far:

I know that if we are looking for a specific element x in the array, the probability of doing it in a certain number of comparisons is $\frac{1}{n}$, since the distribution is uniform. So the average number of comparisons is still $\frac{n + 1}{2}$. (referencing this question's approved answer)

If the element we are looking for x is the duplicate number, however, then what is that probability of doing it in a certain number of comparisons? From there, how would I then compute the average-case complexity?

• To discuss average-case complexity, we must decide what we're taking the average over. So, what is the distribution that the array $A$ and the element $x$ are drawn from? – D.W. Sep 9 '18 at 0:53

Let us assume the elements in the array are the multi-set $M=\{1,2,\cdots,n-k, d, d, \cdots, d\}$, where $d$, an element that is different from $1,2,\cdots, n-k$, appears $k\ge 0$ imes. The situation raised by OP is simply the special case when we let $n=2k$.

In order to discuss the average time-complexity of a linear search, we must specify the distribution of the array as well as the element or the distribution of the element we are searching for.

## The distribution of the array assumed

The most common distribution discussed in various articles and in people's mindset is probably the following simplest one. $$\text{All orderings of the multi-set are equally likely.}$$ That distribution is assumed throughout this answer.

## The average number of comparisons needed when we search for $d$

The following answer is given in the wikipedia analysis.

$$\begin{cases} n & \mbox{if } k = 0 \\ \displaystyle\frac{n + 1}{k + 1} & \mbox{if } 1 \le k \le n. \end{cases}$$

The above answer is easy to prove by induction on $n$.

## The average number of comparisons needed

Assume $k\ge 1$ from now on. Two cases will be shown.

## the case with one extra element

Let $o$ stands for an element not in the set $S=\{1,2,\cdots,n-k, d\}$. If we are searching for a specified element in $S\cup\{o\}$, where each element is equally likely to be specified, here is the computation. \begin{align} E[\text{search for } x] &= \sum_{x!=d \text { and } x!=0}\frac 1{n-k+2}E[\text{search for }x] + \frac1{n-k+2}E[\text{search for }d] + \frac1{n-k+2}E[\text{search for }o]\\ &=\frac{n-k}{n-k+2}\frac{n+1}2 + \frac1{n-k+2}\frac{n + 1}{k + 1} + \frac1{n-k+2}n\\ &=\frac{n+1}2 + \frac1{k+1} - \frac{2}{(k+1)(n-k+2)} \end{align}

In particular, if we let $n=2k$, then $$E[\text{search for } x] =\frac {n+1}2 + \frac2{n+2}-\frac{8}{(n+2)(n+4)}$$

## the case with $M$ alone

What is the average number of comparisons need among the cases when the element we are search for turned out to be an element in $M$, assuming that we are searching for an element in the union of the multi-set $M$ and another multi-set $M'$ that is disjoint with $M$, where all elements in $M$ will be equally likely to be searched? The inclusion of the $M'$ is to ensure that we do NOT know whether the element to be found belongs to $M$ before we start the search.

Here is the computation. \begin{align} E[\text{search for } x] &= \sum_{x!=d}\frac 1{n}E[\text{search for }x] + \frac k{n}E[\text{search for }d]\\ &=\frac{n-k}n\frac{n+1}2 + \frac k{n}\frac{n + 1}{k + 1}\\ &=\left(1-\frac{k-2}n -\frac2{n(k+1)}\right)\frac {n+1}2 \end{align}

In particular, if we let $n=2k$, then $$E[\text{search for } x] =\frac14\left(n+5-\frac 4{n+2}\right)$$

Please note that we have not computed the situations when we know the element to be searched is an element of array before we start the linear search, which might be the more common situations. Readers are encouraged to dive into those situations.

The wikipedia item is a good place to start your journey of finding, reading, and playing with the many variations and generalization of this question.

• Thank you for the detailed explanation. In your answer you mentioned that the average number of comparisons needed when we search for d can be given by the Wikipedia answer's system of equations. I understand how to prove the first one by induction on n, but how do we prove the case where 1 <= k <= n? – M. Twain Sep 11 '18 at 18:04
• Oops, I am just now realizing that both of those proofs are the same thing... we can rewrite k in terms of n (more specifically, k = n/2)... – M. Twain Sep 11 '18 at 18:46
• Yes, I am glad you made it. – Apass.Jack Sep 11 '18 at 18:47