# Average-case analysis of linear search given that the desired element appears $k$ times

The problem below is adapted from CLRS Problem 5-2 "Searching an unsorted array":

Consider a deterministic linear search algorithm which searches an array $A$ for $x$ in order, say $A, A, \ldots, A[n]$, until either it finds $A[i] = x$ or it reaches the end of the array. Assume that all possible permutations of the input array are equally likely.

Suppose that there are $k \ge 1$ indices $i$ such that $A[i] = x$. What is the average-time running time of this algorithm?

Let $X$ be a random variable denoting the number of comparisons.

\begin{align*} E(X) &= \sum_{i=1}^{i=n-k+1} i \cdot \Pr(X = i) \\ &= \sum_{i=1}^{i=n-k+1} i \cdot \left(\frac{n-k}{n} \cdot \frac{n-k-1}{n-1} \cdot \frac{n-k-2}{n-2} \cdot \cdots \cdot \frac{n-k-i+2}{n-i+2} \cdot \frac{k}{n-i+1}\right) \end{align*}

How to evaluate this summation? Or is there a simple solution to this problem?

Note that when $k=1$, $E(X)$ is $\frac{n+1}{2}$. When $k=n$, $E(X)$ is $1$.

Note \begin{align*} E(X)&=\sum_{i=1}^{n-k+1} i \cdot \Pr(X = i)\\ &=\sum_{i=1}^{n-k+1} \sum_{j=1}^i\Pr(X = i)\\ &=\sum_{j=1}^{n-k+1} \sum_{i=j}^{n-k+1}\Pr(X = i)\\ &=\sum_{j=1}^{n-k+1} \Pr(X \ge j), \end{align*} and $X\ge j$ means all $x$ are distributed among $A[j],\ldots,A[n]$, so $$\Pr(X \ge j)=\frac{\binom{n-j+1}{k}}{\binom{n}{k}}.$$ Therefore $$E(X)=\sum_{j=1}^{n-k+1} \frac{\binom{n-j+1}{k}}{\binom{n}{k}}=\frac{1}{\binom{n}{k}}\sum_{r=k}^{n}\binom{r}{k}=\frac{1}{\binom{n}{k}}\binom{n+1}{k+1}=\frac{n+1}{k+1}.$$
• $$\sum_{r=k}^{n}\binom{r}{k}=\binom{n+1}{k+1}$$ . Is this some property of combinatorics?
• @VK It's a corollary of $\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}$: $\binom{k}{k}+\binom{k+1}{k}+\cdots=\binom{k+1}{k+1}+\binom{k+1}{k}+\cdots=\binom{k+2}{k+1}+\binom{k+2}{k}+\cdots=\binom{k+3}{k+1}+\binom{k+3}{k}+\cdots=\cdots=\binom{n+1}{k+1}$. Jul 21, 2020 at 9:39