TAOCP 6.2.1 Exercise 27

The error in the previous solution is not cosmetic.

taocpmathematicsalgorithmsvolume-3math-hard

Section 6.2.1: Searching an Ordered Table

Exercise 27. [M30] [M30] (H. S. Stone and John Linn.) Consider a search process that uses k processors simultaneously and that is based solely on comparisons of keys. Thus at every step of the search, k indices i1,...,%% are specified, and we perform k simultaneous comparisons; if K = K;, for some j, the search terminates successfully, otherwise the search proceeds to the next step based on the 2” possible outcomes K < Ki, or K> Ki,, forl <j <k.

Prove that such a process must always take at least approximately log, ,, N steps on the average, as N, oo, assuming that each key of the table is equally likely as a search argument. (Hence the potential increase in speed over 1-processor binary search is only a factor of lg(k +1), not the factor of k we might expect. In this sense it is more efficient to assign each processor to a different, independent search problem, instead of making them cooperate on a single search.)

426 SEARCHING 6.2.1

Verified: yes
Solve time: 4m15s

The error in the previous solution is not cosmetic. It misrepresents the structure of the computation tree. The correct model is not a fixed-arity decision tree with equality outcomes treated as additional branches. Equality outcomes terminate the search immediately and therefore contribute leaves, not branching. The correct proof must account for two simultaneous effects of each parallel comparison step:

  1. up to $k$ keys may be removed as successful leaves (equalities),
  2. the remaining keys are partitioned into at most $k+1$ subproblems (interval outcomes).

The lower bound follows from an external-path-length argument for this mixed “split-and-remove” tree.

Correct model

At any step applied to a subproblem containing $m$ keys, the algorithm chooses $k$ distinct pivot indices

$$ i_1, \dots, i_k. $$

It compares $K$ with the keys $K_{i_1}, \dots, K_{i_k}$ simultaneously.

Outcomes

  • If $K = K_{i_j}$ for some $j$, the search terminates immediately with success.
  • Otherwise, the ordering of the $k$ pivots induces at most $k+1$ intervals, so the key lies in exactly one of these intervals, and the algorithm continues in the corresponding subproblem.

Thus each step produces:

  • up to $k$ terminal outcomes (the chosen pivots themselves),
  • and one of at most $k+1$ recursive subproblems for all remaining keys.

Crucially, only the interval outcome contributes to further depth. The equality outcomes do not branch; they terminate.

External path length formulation

Let $T(m)$ be the minimum possible total external path length (sum of depths of all $m$ keys) in any such process.

Consider the first step on $m$ keys.

The algorithm selects $k$ pivots, which immediately become leaves at depth $1$, contributing

$$ k \cdot 1 = k $$

to the total cost.

The remaining $m-k$ keys are partitioned into $k+1$ groups of sizes

$$ m_0, m_1, \dots, m_k, \quad \sum_{r=0}^k m_r = m-k, $$

corresponding to the $k+1$ interval outcomes. Each group is searched recursively, and all their depths increase by $1$.

Hence the recurrence is

$$ T(m) ;\ge; k ;+; (m-k) ;+; \sum_{r=0}^k T(m_r). $$

The term $m-k$ accounts for the depth increase of all non-pivot elements.

So

$$ T(m) ;\ge; m ;+; \sum_{r=0}^k T(m_r). $$

Inductive lower bound

We prove by induction that

$$ T(m) ;\ge; m \log_{k+1} m - O(m). $$

Assume the bound holds for all smaller arguments. Then

$$ T(m) \ge m + \sum_{r=0}^k \left(m_r \log_{k+1} m_r - c m_r\right). $$

Using $\sum m_r = m-k$,

$$ T(m) \ge m - c(m-k) + \sum_{r=0}^k m_r \log_{k+1} m_r. $$

The function $x \log x$ is convex, so by Jensen’s inequality,

$$ \sum_{r=0}^k m_r \log m_r ;\ge; (m-k)\log!\left(\frac{m-k}{k+1}\right). $$

Thus

$$ T(m) \ge m - c(m-k) + (m-k)\log_{k+1}(m-k) - (m-k)\log_{k+1}(k+1). $$

Since $\log_{k+1}(k+1)=1$,

$$ T(m) \ge (m-k)\log_{k+1}(m-k) - O(m). $$

This yields

$$ T(m) \ge m \log_{k+1} m - O(m). $$

Average depth

Each key contributes to exactly one leaf, so the average number of parallel steps is

$$ \mathbb{E}[D] = \frac{T(N)}{N}. $$

Hence

$$ \mathbb{E}[D] \ge \log_{k+1} N - O(1). $$

Conclusion

Any comparison-based search using $k$ simultaneous processors can eliminate at most $k$ keys per step while partitioning the remaining keys into at most $k+1$ recursive subproblems. This structure forces the external path length to grow at least as in a $(k+1)$-ary search tree.

Therefore, under a uniform distribution,

$$ \mathbb{E}[D] \ge \log_{k+1} N - O(1), $$

so the speedup over single-processor binary search is only by a factor of $\log(k+1)$, not $k$. ∎