TAOCP 7.2.1.2 Exercise 48
Algorithm $X$ and Algorithm $L$ both enumerate all $n!$ permutations of $a_1 a_2 \dots a_n$.
Section 7.2.1.2: Generating All Permutations
Exercise 48. ▶ [M25] [M25] Compare the running times of Algorithm X and Algorithm L, in the case when the tests t1(a1), t2(a1, a2), . . . , tn(a1, a2, . . . , an) always are true.
Verified: no
Solve time: 2m22s
Solution
Algorithm $X$ and Algorithm $L$ both enumerate all $n!$ permutations of $a_1 a_2 \dots a_n$. The difference lies in the amount of work performed per visited node and, in particular, in how many feasibility tests $t_k(a_1,\dots,a_k)$ are executed when these tests are identically true.
For Algorithm $X$, the computation can be viewed as a full expansion of the permutation construction tree. At depth $k$, a partial prefix $(a_1,\dots,a_k)$ is formed, and all $n-k$ remaining elements are still available for extension. Because every test $t_k$ is assumed always true, every possible prefix is extended without pruning. Hence, at depth $k$ there are exactly
$$ \frac{n!}{(n-k)!} $$
nodes corresponding to ordered choices of $k$ distinct elements.
At each such node, Algorithm $X$ performs a constant amount of control work plus the evaluation of the prefix condition at level $k$. Since the hypothesis states all tests are true, each such evaluation still occurs exactly once per node. Therefore the total number of test evaluations of level $k$ is $\frac{n!}{(n-k)!}$, and the total number of test evaluations over the entire execution is
$$ T_X = \sum_{k=1}^{n} \frac{n!}{(n-k)!}. $$
Rewriting with the substitution $j=n-k$ gives
$$ T_X = \sum_{j=0}^{n-1} \frac{n!}{j!} = n! \sum_{j=0}^{n-1} \frac{1}{j!}. $$
The sum $\sum_{j=0}^{n-1} \frac{1}{j!}$ is bounded above by $e$ and increases monotonically toward $e$, so it remains $\Theta(1)$ as $n$ grows. However, this expression counts only the testing work per node. Each node at depth $k$ also incurs $k$ units of prefix-management work, since $k$ elements are involved in the state of the partial permutation. Accounting for this structural cost gives
$$ W_X = \sum_{k=1}^{n} k \cdot \frac{n!}{(n-k)!}. $$
Reindexing with $j=n-k$ yields
$$ W_X = \sum_{j=0}^{n-1} (n-j)\frac{n!}{j!} = n! \left( n \sum_{j=0}^{n-1} \frac{1}{j!} - \sum_{j=0}^{n-1} \frac{j}{j!} \right). $$
The second sum simplifies by the identity $\frac{j}{j!} = \frac{1}{(j-1)!}$ for $j \ge 1$, giving
$$ \sum_{j=0}^{n-1} \frac{j}{j!} = \sum_{i=0}^{n-2} \frac{1}{i!}. $$
Substituting this into the expression for $W_X$ yields
$$ W_X = n!\left( n \sum_{j=0}^{n-1} \frac{1}{j!} - \sum_{i=0}^{n-2} \frac{1}{i!} \right). $$
Both sums converge to constants bounded by $e$, and their difference leaves a leading term proportional to $n$. The dominant growth rate is therefore
$$ W_X = \Theta(n \cdot n!). $$
Algorithm $L$ generates permutations in lexicographic order. Each transition between consecutive permutations is performed by a bounded amount of local modification determined by the standard next-permutation mechanism. In particular, each step changes a suffix and performs a bounded number of swaps and comparisons whose total amortized cost per permutation remains constant when the full sequence is traversed without backtracking or failed tests. Since Algorithm $L$ performs exactly $n!-1$ transitions and each transition contributes $\Theta(1)$ amortized work under the assumption that no tests fail and no backtracking occurs, the total running time satisfies
$$ W_L = \Theta(n!). $$
Comparing the two results,
$$ W_X = \Theta(n \cdot n!), \qquad W_L = \Theta(n!), $$
so Algorithm $X$ requires an additional multiplicative factor of order $n$ in the total running time under the stated condition that all prefix tests are true.
This completes the solution. ∎