TAOCP 6.1 Exercise 1
In a successful sequential search through $N$ records, every position $i \in {1,\dots,N}$ occurs with probability $1/N$.
Section 6.1: Sequential Searching
Exercise 1. [M20] [M20] When all the search keys are equally probable, what is the standard deviation of the number of comparisons made in a successful sequential search through a table of N records?
Verified: yes
Solve time: 1m01s
Solution
In a successful sequential search through $N$ records, every position $i \in {1,\dots,N}$ occurs with probability $1/N$. The number of comparisons is therefore the random variable $C = i$.
The expected value is
$$ \mathbb{E}[C] = \frac{1}{N}\sum_{i=1}^N i = \frac{N+1}{2}. $$
The second moment is obtained from the standard identity
$$ \sum_{i=1}^N i^2 = \frac{N(N+1)(2N+1)}{6}, $$
hence
$$ \mathbb{E}[C^2] = \frac{1}{N}\sum_{i=1}^N i^2 = \frac{(N+1)(2N+1)}{6}. $$
The variance is
$$ \mathrm{Var}(C) = \mathbb{E}[C^2] - (\mathbb{E}[C])^2 = \frac{(N+1)(2N+1)}{6} - \frac{(N+1)^2}{4}. $$
Factoring $(N+1)$ gives
$$ \mathrm{Var}(C) = (N+1)\left(\frac{2N+1}{6} - \frac{N+1}{4}\right). $$
With common denominator $12$,
$$ \frac{2N+1}{6} - \frac{N+1}{4} = \frac{4N+2 - 3N - 3}{12} = \frac{N-1}{12}. $$
Thus
$$ \mathrm{Var}(C) = \frac{(N+1)(N-1)}{12} = \frac{N^2 - 1}{12}. $$
The standard deviation is therefore
$$ \sqrt{\mathrm{Var}(C)} = \sqrt{\frac{N^2 - 1}{12}}. $$
This completes the proof. ∎