TAOCP 6.1 Exercise 7

Section 6.1: Sequential Searching

Exercise 7. [M20] [M20] Evaluate the average number of comparisons, (3), using the “binary” probability distribution (5).

Verified: yes
Solve time: 1m01s

---

Solution

The probability distribution (5) is

$$ p_k = 2^{-k}\quad (1 \le k \le N-1), \qquad p_N = 2^{-(N-1)}. $$

The average number of comparisons in a successful search is given by (3):

$$ C_N = \sum_{k=1}^{N} k p_k = \sum_{k=1}^{N-1} \frac{k}{2^k} + \frac{N}{2^{N-1}}. $$

Define

$$ S_m = \sum_{k=1}^{m} \frac{k}{2^k}. $$

Let

$$ f(x) = \sum_{k=1}^{m} x^k = \frac{x(1-x^m)}{1-x}. $$

Differentiation yields

$$ \sum_{k=1}^{m} k x^{k-1} = \frac{1-(m+1)x^m + m x^{m+1}}{(1-x)^2}. $$

Multiplying by $x$ gives

$$ \sum_{k=1}^{m} k x^{k} = \frac{x\left(1-(m+1)x^m + m x^{m+1}\right)}{(1-x)^2}. $$

Substituting $x = \tfrac{1}{2}$ yields

$$ S_m = \frac{\frac{1}{2}\left(1-(m+1)2^{-m} + m 2^{-(m+1)}\right)}{(1-\frac{1}{2})^2}. $$

Since $(1-\tfrac{1}{2})^2 = \tfrac{1}{4}$, this becomes

$$ S_m = 2\left(1-(m+1)2^{-m} + m 2^{-(m+1)}\right). $$

Rewrite the last two terms:

$$ m 2^{-(m+1)} = \frac{m}{2},2^{-m}. $$

Hence

$$ S_m = 2 - 2(m+1)2^{-m} + m 2^{-m} = 2 - (m+2)2^{-m}. $$

Set $m = N-1$:

$$ \sum_{k=1}^{N-1} \frac{k}{2^k} = 2 - (N+1)2^{-(N-1)}. $$

Substitute into $C_N$:

$$ C_N = 2 - (N+1)2^{-(N-1)} + \frac{N}{2^{N-1}} = 2 - 2^{-(N-1)}. $$

Thus

$$ C_N = 2 - 2^{-(N-1)}. $$

This completes the proof. ∎