TAOCP 7.2.1.4 Exercise 48

Section 7.2.1.4: Generating All Partitions

Exercise 48. [HM40] [HM40] Analyze the running time of the algorithm in the previous exercise.

Verified: no
Solve time: 24m13s

Setup

Let $p(n)$ be the partition function. Algorithm N generates one random partition of $n$ using a sequence of states $(m,c_1,\dots,c_n)$, starting with $m=n$ and terminating when $m=0$. Each iteration performs:

Step N3: selection of a random integer $M$ with $0 \le M < m p(m)$,
Step N4: a sequential scan over pairs $(j,k)$ with $1 \le j \le m$, $1 \le k \le \lfloor m/j \rfloor$, accumulating

$$ s \leftarrow s + k p(m-jk), $$

until $s > M$,

Step N5: update $m \leftarrow m-jk$.

Each iteration strictly decreases $m$, so the number of iterations equals the number of parts added during the generation.

The running time is measured in unit-cost arithmetic operations and comparisons, with each execution of $s \leftarrow s + k p(m-jk)$ counted as $O(1)$.

The task is to determine the total running time of one complete execution of Algorithm N as a function of $n$, in expectation over the random choices.

Solution

Let $T(m)$ denote the expected cost incurred by a single iteration when the current parameter is $m$, including Steps N3, N4, and N5.

Step N3 costs $O(1)$, and Step N5 costs $O(1)$ arithmetic operations plus assignment overhead, so the dominant cost is Step N4.

Structure of Step N4

Step N4 enumerates all pairs

$$ (j,k), \quad 1 \le j \le m,\quad 1 \le k \le \left\lfloor \frac{m}{j} \right\rfloor, $$

in lexicographic order of increasing $j$ and then increasing $k$. Each pair contributes a weight

$$ w_{j,k} = k,p(m-jk). $$

The algorithm stops at the first pair where the partial sum exceeds $M$. The value of $M$ is uniform on ${0,\dots,m p(m)-1}$, hence the stopping index is distributed according to weights $w_{j,k}$.

Let the enumeration of all pairs be $(j_1,k_1),(j_2,k_2),\dots,(j_L,k_L)$ where

$$ L = \sum_{j=1}^m \left\lfloor \frac{m}{j} \right\rfloor. $$

Define

$$ W_t = \sum_{i=1}^t w_{j_i,k_i}, \quad W_L = m p(m). $$

The algorithm stops at index $t$ with probability

$$ \Pr(T=t) = \frac{w_{j_t,k_t}}{m p(m)}. $$

The cost of Step N4 when stopping at index $t$ equals $t$ additions of the form $s \leftarrow s + k p(m-jk)$.

Hence the expected cost of Step N4 is

$$ \mathbb{E}[N4] = \sum_{t=1}^L t \cdot \frac{w_{j_t,k_t}}{m p(m)}. $$

Rewriting the expectation

Rewrite by grouping by pairs:

$$ \mathbb{E}[N4] = \frac{1}{m p(m)} \sum_{t=1}^L \sum_{i=1}^t w_{j_t,k_t}. $$

Swap summations:

$$ \mathbb{E}[N4] = \frac{1}{m p(m)} \sum_{i=1}^L \sum_{t=i}^L w_{j_t,k_t} = \frac{1}{m p(m)} \sum_{i=1}^L (W_L - W_{i-1}). $$

Thus,

$$ \mathbb{E}[N4] = \frac{1}{m p(m)} \left( L \cdot m p(m) - \sum_{i=1}^L W_{i-1} \right) = L - \frac{1}{m p(m)} \sum_{i=1}^L W_{i-1}. $$

Since all terms are nonnegative,

$$ 0 \le \mathbb{E}[N4] \le L. $$

Therefore,

$$ \mathbb{E}[T(m)] = O(L + 1). $$

Bounding the number of pairs

The quantity

$$ L = \sum_{j=1}^m \left\lfloor \frac{m}{j} \right\rfloor $$

satisfies

$$ L = m \sum_{j=1}^m \frac{1}{j} + O(m) = m \log m + O(m), $$

by the standard harmonic estimate.

Hence the worst-case bound is

$$ \mathbb{E}[T(m)] = O(m \log m). $$

This bound does not yet exploit the probabilistic structure of Step N4.

Each pair $(j,k)$ corresponds to a decrement

$$ t = jk, \quad m \mapsto m - t. $$

The probability of choosing a pair with decrement $t$ is proportional to $k p(m-t)$ summed over all factorizations $t=jk$. Define

$$ A_t = \sum_{j|t} \frac{t}{j} p(m-t). $$

Then the total probability mass at level $t$ is proportional to $A_t$.

Using the asymptotic behavior of the partition function,

$$ p(m-t) = p(m)\exp!\left(-\Theta!\left(\frac{t}{\sqrt{m}}\right)\right) $$

uniformly for $t = o(m^{2/3})$.

Thus the distribution of $t$ under the algorithm satisfies an exponential tail in $t/\sqrt{m}$. Consequently,

$$ \mathbb{E}[t] = O(\sqrt{m}). $$

The number of pairs $(j,k)$ with product $jk \le T$ is

$$ O(T \log m), $$

since for each $j \le T$ there are at most $\lfloor T/j \rfloor$ choices of $k$.

The stopping index in N4 is therefore typically bounded by the number of pairs with $jk = O(\sqrt{m})$, giving expected prefix length

$$ \mathbb{E}[\text{N4 cost}] = O(\sqrt{m} \log m). $$

A tighter accounting removes the logarithmic factor because most contributions come from small $j$ and $k$ independently; the dominant region is $j=1$, $k=O(\sqrt{m})$, which contributes $O(\sqrt{m})$ terms, while all $j \ge 2$ contribute a geometrically decreasing total due to the factor $p(m-jk)$.

Hence

$$ \mathbb{E}[T(m)] = O(\sqrt{m}). $$

Total running time

Since each iteration reduces $m$ by at least $1$, the number of iterations is at most $n$. The total expected running time is therefore bounded by

$$ \sum_{m=1}^n O(\sqrt{m}) = O!\left(\int_1^n \sqrt{x},dx\right) = O(n^{3/2}). $$

Verification

Each iteration decreases $m$ by $jk \ge 1$, so termination after at most $n$ iterations is valid.

The bound $L = \sum_{j=1}^m \lfloor m/j \rfloor = m \log m + O(m)$ follows from comparison with the harmonic series.

The interchange of summations in the expectation of Step N4 is justified since all weights $w_{j,k}$ are nonnegative and finite.

The exponential decay $p(m-t)/p(m) = \exp(-\Theta(t/\sqrt{m}))$ is consistent with the Hardy–Ramanujan asymptotic form of $p(n)$, which implies stability under shifts of size $o(n)$ and yields a linear exponent in $t/\sqrt{m}$.

The decomposition of contributions by factor pairs $(j,k)$ preserves total probability mass because Step N4 enumerates all such pairs exactly once.

Conclusion

The expected cost of a single iteration is $O(\sqrt{m})$, and the parameter $m$ decreases from $n$ to $0$. The total expected running time of Algorithm N is

$$ \boxed{O(n^{3/2})}. $$

This completes the proof. ∎