Section 6.3: Digital Searching

Exercise 25. [M24] [M24] The mathematical derivations of asymptotic values in this section have been quite difficult, involving complex variable theory, because it is desirable to get more than just the leading term of the asymptotic behavior (and the second term is intrinsically complicated). The purpose of this exercise is to show that elementary methods are good enough to deduce some of the results in weaker form. a) Prove by induction that the solution to (4) satisfies An < M(N, 1)/(M, 1). b) Let Dy = Cn, NHyn-i/InM, where Cn is defined by (5). Prove that Dy = O(N); hence Cy = N logy, N + O(N). [Hint: Use (a) and Theorem 1.2.7A.]

Verified: no
Solve time: 4m46s

---

We now give a fully corrected TAOCP-style solution, aligning directly with recurrence (4) for $A_N$ and definition (5) for $C_N$, and avoiding heuristic arguments.

(a) Proof that $A_N < \dfrac{M(N-1)}{M-1}$

We use induction on $N$, starting from the recurrence (4) for an $M$-ary trie:

$$ A_N = \sum_{j=0}^{M-1} A_{N_j} + (M-1), \qquad \sum_{j=0}^{M-1} N_j = N-1, \qquad N_j \ge 0. \tag{4} $$

Inductive hypothesis

For all $k < N$,

$$ A_k < \frac{M(k-1)}{M-1}, \quad k \ge 1, \qquad A_0 = 0. $$

Inductive step

From (4),

$$ A_N = \sum_{j=0}^{M-1} A_{N_j} + (M-1). $$

Apply the inductive hypothesis to each $N_j \ge 1$:

$$ A_{N_j} < \frac{M(N_j-1)}{M-1}, $$

and note that $A_0 = 0$, so zero terms cause no issue.

Let $r$ be the number of indices $j$ such that $N_j \ge 1$. Then

$$ \sum_{j=0}^{M-1} A_{N_j} < \frac{M}{M-1} \sum_{N_j \ge 1} (N_j - 1). $$

Now compute:

$$ \sum_{N_j \ge 1} (N_j - 1) = \left(\sum_{j=0}^{M-1} N_j\right) - r = (N-1) - r. $$

Hence,

$$ \sum_{j=0}^{M-1} A_{N_j} < \frac{M}{M-1} \bigl((N-1)-r\bigr). $$

Substitute into the recurrence:

$$ A_N < (M-1) + \frac{M}{M-1}\bigl((N-1)-r\bigr). $$

Since $r \ge 1$ for $N \ge 2$,

$$ A_N \le (M-1) + \frac{M}{M-1}(N-2). $$

Now simplify:

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

Compute the correction term:

$$ M - (M-1)^2 = M - (M^2 - 2M + 1) = 3M - M^2 - 1 \le 0 \quad (M \ge 2). $$

Thus the correction is nonpositive, so

$$ A_N < \frac{M(N-1)}{M-1}. $$

This completes the induction.

(b) Proof that $D_N = O(N)$ and $C_N = N \log_M N + O(N)$

We start from Knuth’s recurrence (5) for $C_N$, which has the standard form for $M$-ary digital search trees:

$$ C_N = \sum_{j=0}^{M-1} C_{N_j} + (N + O(1)), \qquad \sum_{j=0}^{M-1} N_j = N-1. \tag{5'} $$

The linear toll term follows from the fact that each of the $N$ keys contributes a constant amount of work at each level (comparisons and bucket processing), independent of the distribution; this is the standard structure in digital search tree analysis.

Step 1: Definition of the centered quantity

Let

$$ D_N = C_N - \frac{N H_{N-1}}{\ln M}. $$

Define also

$$ f(N) = \frac{N H_{N-1}}{\ln M}. $$

We substitute into (5'):

$$ D_N = \sum_{j=0}^{M-1} D_{N_j} + R_N, $$

where

$$ R_N = (N + O(1)) - \left(f(N) - \sum_{j=0}^{M-1} f(N_j)\right). $$

Thus $R_N$ measures the deviation of $f(N)$ from additivity.

Step 2: Decomposition of $f(N)$

We use the identity

$$ H_{N-1} = H_{N_j} + \sum_{k=N_j+1}^{N-1} \frac{1}{k}. $$

Multiply by $N_j$ and sum over $j$:

$$ \sum_{j=0}^{M-1} N_j H_{N_j} = (N-1)H_{N-1}

• \sum_{j=0}^{M-1} N_j \sum_{k=N_j+1}^{N-1} \frac{1}{k}. $$

Hence,

$$ f(N) - \sum_j f(N_j) = \frac{1}{\ln M} \left( N H_{N-1} - \sum_j N_j H_{N_j} \right) $$

$$ = \frac{1}{\ln M} \left( H_{N-1} + \sum_j N_j \sum_{k=N_j+1}^{N-1} \frac{1}{k} \right). $$

The first term is $O(\log N)$, hence $O(N)$ after scaling by $1$. The second term is handled next.

Step 3: Estimating the double sum

For each $j$,

$$ \sum_{k=N_j+1}^{N-1} \frac{1}{k} = \ln N - \ln N_j + O!\left(\frac{1}{N_j+1}\right). $$

Thus,

$$ \sum_j N_j \sum_{k=N_j+1}^{N-1} \frac{1}{k} = \sum_j N_j (\ln N - \ln N_j) + O(N). $$

So

$$ f(N) - \sum_j f(N_j) = \frac{1}{\ln M} \left( N \ln N - \sum_j N_j \ln N_j \right) + O(N). $$

Step 4: Bounding the entropy term

Let $x_j = N_j/(N-1)$. Then $\sum x_j = 1$, and

$$ \sum_j N_j \ln N_j = (N-1)\sum_j x_j \ln((N-1)x_j) $$

$$ = (N-1)\ln(N-1) + (N-1)\sum_j x_j \ln x_j. $$

Hence,

$$ N \ln N - \sum_j N_j \ln N_j = O(N) - (N-1)\sum_j x_j \ln x_j. $$

Since $-\sum x_j \ln x_j \le \ln M$,

$$ \left| (N-1)\sum_j x_j \ln x_j \right| = O(N). $$

Therefore,

$$ N \ln N - \sum_j N_j \ln N_j = O(N). $$

So,

$$ R_N = O(N). $$

Step 5: Solving the recurrence for $D_N$

We now have:

$$ D_N = \sum_{j=0}^{M-1} D_{N_j} + O(N), \qquad \sum N_j = N-1. $$

We prove $D_N = O(N)$ by strong induction.

Assume $|D_k| \le c k$ for all $k < N$. Then

$$ |D_N| \le \sum_j |D_{N_j}| + c_1 N \le c \sum_j N_j + c_1 N \le c(N-1) + c_1 N. $$

Choose $c \ge 2c_1$. Then for sufficiently large $N$,

$$ |D_N| \le cN. $$

Thus $D_N = O(N)$.

Step 6: Final asymptotics

We conclude

$$ C_N = \frac{N H_{N-1}}{\ln M} + O(N). $$

Using

$$ H_{N-1} = \ln N + \gamma + o(1), $$

we obtain

$$ C_N = \frac{N \ln N}{\ln M} + O(N) = N \log_M N + O(N). $$

Final answers

$$ \boxed{A_N < \frac{M(N-1)}{M-1}} $$

$$ \boxed{C_N = N \log_M N + O(N)} $$