TAOCP 6.3 Exercise 23

Section 6.3: Digital Searching

Exercise 23. [M26] [M26] How many digit inspections are made on the average during an unsuccessful search in an M-ary trie containing N random keys?

Verified: yes
Solve time: 1m23s

---

Setup

Let $N$ keys be stored in an $M$-ary trie under the uniform random model in which each digit of each key is independently uniformly distributed in ${0,1,\dots,M-1}$. A search argument $K$ is assumed to be an infinite random sequence of independent digits with the same distribution, independent of the stored keys.

During an unsuccessful search, the algorithm inspects one digit of $K$ at each level of the trie until it reaches a node $P$ such that the corresponding table entry for the next digit is null. The number of digit inspections equals the depth of the deepest node reached along the path determined by the successive prefixes of $K$.

Let $D_N$ denote the random variable equal to the number of digit inspections in an unsuccessful search in a trie containing $N$ keys. The goal is to determine $\mathbb{E}[D_N]$ asymptotically as $N \to \infty$.

Solution

For each level $j \ge 0$, let $A_j$ be the event that the search reaches level $j$, meaning that the prefix of $K$ of length $j$ matches at least one key prefix among the $N$ stored keys. Then

$$ D_N = \sum_{j \ge 0} \mathbf{1}_{A_j}, $$

so

$$ \mathbb{E}[D_N] = \sum_{j \ge 0} \mathbb{P}(A_j). $$

At level $j$, there are $M^j$ possible prefixes of length $j$. Each stored key has probability $M^{-j}$ of matching a fixed prefix. Hence the probability that no stored key matches a given prefix is $(1 - M^{-j})^N$. The search reaches level $j$ precisely when the prefix of $K$ of length $j$ matches at least one stored key prefix, so

$$ \mathbb{P}(A_j) = 1 - (1 - M^{-j})^N. $$

Thus

$$ \mathbb{E}[D_N] = \sum_{j \ge 0} \left(1 - (1 - M^{-j})^N \right). $$

Let $L = \lfloor \log_M N \rfloor$. For $j \le L$, $N M^{-j} \ge 1$, and

$$ (1 - M^{-j})^N \le e^{-N M^{-j}}, $$

so $\mathbb{P}(A_j) = 1 - (1 - M^{-j})^N = 1 - O(e^{-N M^{-j}}) = 1 + O(e^{-N M^{-j}})$, which contributes $1 + o(1)$ per level in this range.

For $j \ge L + c$ with fixed $c \ge 1$, one has $N M^{-j} \le M^{-c}$, hence

$$ \mathbb{P}(A_j) = 1 - (1 - M^{-j})^N = N M^{-j} + O(N^2 M^{-2j}). $$

The tail sum over $j \ge L + c$ is bounded by a convergent geometric series of order $M^{-c}$.

Therefore the main contribution comes from levels $0,1,\dots,L$, each contributing approximately $1$, while all remaining levels contribute a bounded total independent of $N$. This yields

$$ \mathbb{E}[D_N] = L + O(1). $$

Since $L = \lfloor \log_M N \rfloor$, this becomes

$$ \mathbb{E}[D_N] = \frac{\ln N}{\ln M} + O(1). $$

Thus the average number of digit inspections in an unsuccessful search is

$$ \boxed{\frac{\ln N}{\ln M} + O(1)}. $$

This completes the proof. ∎

Verification

The decomposition $D_N = \sum_{j \ge 0} \mathbf{1}_{A_j}$ is valid because exactly one digit is inspected per level reached, and the search proceeds level by level until failure.

The expression $\mathbb{P}(A_j) = 1 - (1 - M^{-j})^N$ follows from independence of key digits, since each key matches a fixed prefix of length $j$ with probability $M^{-j}$.

The splitting at $L = \lfloor \log_M N \rfloor$ separates the regime where expected occupancy $N M^{-j}$ is large from the regime where it is small, ensuring bounded contribution from both tails and logarithmic main growth.

Notes

The same argument shows that successful and unsuccessful searches in random tries have identical leading-order behavior $\log_M N$, since both are governed by the depth at which prefix occupancy drops from high probability to low probability.