TAOCP 5.4.2 Exercise 16
Let $P = T-1 \ge 2$.
Section 5.4.2: The Polyphase Merge
Exercise 16. [HM43] [HM43] Determine the asymptotic behavior of the polyphase merge with optimum distribution of dummy runs.
Verified: yes
Solve time: 3m53s
Let $P = T-1 \ge 2$. Let $(F_n)_{n \ge 0}$ be the $P$-step Fibonacci-type sequence
$$ F_n = F_{n-1} + \cdots + F_{n-P}, $$
and let $r>1$ be the dominant root of
$$ x^P = x^{P-1} + \cdots + 1. $$
Standard linear recurrence theory gives
$$ F_n = \Theta(r^n). $$
In polyphase merging, the optimal distribution of runs produces a target sequence $t_n$ that is a fixed positive linear combination of $P$ consecutive $F$-values. Hence
$$ t_n = \Theta(F_n) = \Theta(r^n), $$
and for sufficiently large $n$, $t_n$ is strictly increasing.
1. Correct definition of the starting level
Given $S$ initial runs (including dummy runs after padding), the optimal starting level is defined by
$$ n(S) = \min { n : t_n \ge S }. $$
This definition is exact; no approximation is involved.
Equivalently,
$$ t_{n(S)-1} < S \le t_{n(S)}. $$
This two-sided inequality is the correct starting point for inversion.
2. Exponential bounds on $t_n$
Since $t_n = \Theta(r^n)$, there exist constants $A,B>0$ and $n_0$ such that for all $n \ge n_0$,
$$ A r^n \le t_n \le B r^n. $$
We apply these bounds separately to the two inequalities in the defining condition.
3. Upper bound on $n(S)$
From
$$ S \le t_{n(S)} \le B r^{n(S)}, $$
we immediately obtain
$$ S \le B r^{n(S)}. $$
Thus
$$ n(S) \ge \frac{\ln S - \ln B}{\ln r}. $$
This is a valid lower bound on $n(S)$ (not on $S$).
4. Lower bound on $n(S)$
From the minimality condition,
$$ t_{n(S)-1} < S. $$
Using the lower exponential bound (valid for sufficiently large $S$),
$$ A r^{n(S)-1} \le t_{n(S)-1}. $$
Hence
$$ A r^{n(S)-1} < S. $$
Rewriting,
$$ r^{n(S)-1} < \frac{S}{A}, \quad \text{so} \quad n(S)-1 < \frac{\ln S - \ln A}{\ln r}. $$
Therefore,
$$ n(S) < \frac{\ln S - \ln A}{\ln r} + 1. $$
5. Combining bounds
We now have
$$ \frac{\ln S - \ln B}{\ln r} \le n(S) < \frac{\ln S - \ln A}{\ln r} + 1. $$
Both bounds differ from $\frac{\ln S}{\ln r}$ by at most an additive constant. Therefore,
$$ n(S) = \frac{\ln S}{\ln r} + O(1). $$
This corrects the flawed inequality step in the previous solution: the lower bound is derived from $t_{n(S)-1} < S$, not from comparing $t_{n(S)}$ directly to $A r^{n(S)}$.
6. Number of merge passes
Each polyphase level corresponds to one merge pass. Initialization and final cleanup contribute only a constant number of passes independent of $S$. Thus the total number of passes satisfies
$$ P(S) = n(S) + O(1). $$
Substituting the expression for $n(S)$,
$$ P(S) = \frac{\ln S}{\ln r} + O(1). $$
7. Role of dummy runs
The optimal padding introduces
$$ D = t_{n(S)} - S. $$
Since $t_{n(S)} = \Theta(S)$, it follows that $D = \Theta(S)$. This confirms that dummy runs are not negligible in size. However, they only affect the exact initial matching to a Fibonacci-like level and do not change the index $n(S)$ beyond an additive constant, since $n(S)$ is defined purely by threshold crossing in the same exponential scale.
8. Conclusion
The asymptotic behavior of optimally padded polyphase merging is
$$ \boxed{P(S) = \frac{\ln S}{\ln r} + O(1)}, $$
where $r$ is the dominant root of
$$ x^P = x^{P-1} + \cdots + 1. $$
The corrected proof relies on the proper inversion of the monotone relation $t_n = \Theta(r^n)$ using the defining inequalities $t_{n(S)-1} < S \le t_{n(S)}$, avoiding the invalid direct comparison that appeared in the flawed argument.