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[1], A[2], \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$.


1 Answer 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}. $$

  • $\begingroup$ $$\sum_{r=k}^{n}\binom{r}{k}=\binom{n+1}{k+1}$$ . Is this some property of combinatorics? $\endgroup$
    – V K
    Jul 20, 2020 at 4:17
  • $\begingroup$ @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}$. $\endgroup$
    – xskxzr
    Jul 21, 2020 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.