TAOCP 6.2.1 Exercise 20
Let $C(N)=\log_b N$ for a constant $b>1$ to be determined.
Section 6.2.1: Searching an Ordered Table
Exercise 20. [M22] [M22] The number of comparisons required in a binary search is approximately log, N, and in the Fibonaccian search it is roughly (¢/V/5) log, N. The purpose of this exercise is to show that these formulas are special cases of a more general result.
Let p and q be positive numbers with p+q = 1. Consider a search algorithm that, given a table of N numbers in increasing order, starts by comparing the argument with the (pN)th key, and iterates this procedure on the smaller blocks. (The binary search has p = q = 1/2; the Fibonaccian search has p = 1/4, ¢ = 1/¢”.)
If C(N) denotes the average number of comparisons required to search a table of size N, it approximately satisfies the relations
C(1) = 0; C(N) =1+pC(pN)+qC(qN) for N>1.
This happens because there is probability p (roughly) that the search reduces to a pN-element search, and probability q that it reduces to a gN-element search, after the first comparison. When N is large, we may ignore the small-order effect caused by the fact that pN and qN aren’t exactly integers.
a) Show that C(NV) = log, N satisfies these relations exactly, for a certain choice of b. For binary and Fibonaccian search, this value of b agrees with the formulas derived earlier.
b) Consider the following argument: “With probability p, the size of the interval being scanned in this algorithm is divided by 1/p; with probability q, the interval size is divided by 1/q. Therefore the interval is divided by p- (1/p) + q- (1/q¢) = 2 on the average, so the algorithm is exactly as good as the binary search, regardless of p and q.” Is there anything wrong with this reasoning?
6.2.1 SEARCHING AN ORDERED TABLE 425
Verified: yes
Solve time: 1m17s
Solution
(a)
Let $C(N)=\log_b N$ for a constant $b>1$ to be determined. Then $C(1)=\log_b 1=0$.
For $N>1$, substitute into the recurrence: [ C(N)=1+pC(pN)+qC(qN). ]
The right-hand side becomes [ 1+p\log_b(pN)+q\log_b(qN). ]
Expand logarithms: [ \log_b(pN)=\log_b p+\log_b N,\quad \log_b(qN)=\log_b q+\log_b N. ]
Hence [ \begin{aligned} 1+pC(pN)+qC(qN) &=1+p(\log_b p+\log_b N)+q(\log_b q+\log_b N) \ &=1+(p+q)\log_b N+p\log_b p+q\log_b q \ &=1+\log_b N+p\log_b p+q\log_b q. \end{aligned} ]
Equality with $C(N)=\log_b N$ holds exactly when [ \log_b N = 1+\log_b N+p\log_b p+q\log_b q. ]
Cancellation of $\log_b N$ yields [ 0=1+p\log_b p+q\log_b q. ]
Write logarithms in natural base: [ \log_b x=\frac{\ln x}{\ln b}. ]
Then [ \frac{p\ln p+q\ln q}{\ln b}=-1, \quad \text{so} \quad \ln b=-(p\ln p+q\ln q). ]
Thus [ b=\exp!\bigl(-(p\ln p+q\ln q)\bigr)=p^{-p}q^{-q}. ]
Therefore [ \boxed{b=p^{-p}q^{-q}}. ]
This completes the proof. ∎
(b)
The argument that “the interval is divided on average by $p\cdot(1/p)+q\cdot(1/q)=2$, hence the method is equivalent to binary search” replaces a stochastic multiplicative process by an arithmetic mean of scaling factors.
After one comparison, the remaining interval length is $pN$ with probability $p$ and $qN$ with probability $q$. The expected remaining length is [ \mathbb{E}[N_1]=p(pN)+q(qN)=(p^2+q^2)N, ] which is unrelated to $2$ and does not determine the search depth.
The quantity relevant to comparison cost is the logarithmic decrease. After one step, [ \mathbb{E}[\log N_1] = p\log(pN)+q\log(qN) = \log N + p\log p + q\log q. ]
Thus the expected change per comparison is the constant [ p\log p+q\log q, ] which depends on the full distribution $(p,q)$ and not only on the arithmetic mean of the factors $1/p$ and $1/q$.
Binary search corresponds to $p=q=\tfrac12$, where this logarithmic decrement equals $-1$ in base $2$. For general $(p,q)$, the decrement equals $-(p\ln p+q\ln q)/\ln 2$, which differs from $1$ unless $p=q$.
The incorrect step is the replacement of $\mathbb{E}[\log N_1]$ by $\log(\mathbb{E}[N_1])$, or equivalently the substitution of an average multiplicative factor for a logarithmic additive cost. The comparison process is governed by additive changes in $\log N$, not by averages of linear scaling factors.
This completes the solution. ∎