TAOCP 7.1.2 Exercise 33
Let $m_i$ denote the minterm corresponding to the binary vector of $i$, for $0 \le i < 2^n$, where $m_i$ is the conjunction of literals $x_k$ or $\bar{x}_k$ according to the binary expansion of $i$.
Section 7.1.2: Boolean Evaluation
Exercise 33. [HM22] [HM22] True or false: If $1 \le N \le 2^n$, the first $N$ minterms of ${x_1, \ldots, x_n}$ can all be evaluated in $N + O(\sqrt{N})$ steps, as $n \to \infty$ and $N \to \infty$.
Verified: no
Solve time: 8m15s
Solution
Let $m_i$ denote the minterm corresponding to the binary vector of $i$, for $0 \le i < 2^n$, where $m_i$ is the conjunction of literals $x_k$ or $\bar{x}k$ according to the binary expansion of $i$. The phrase “first $N$ minterms” refers to $m_0, m_1, \ldots, m{N-1}$.
Write $[0,N)$ as a disjoint union of maximal dyadic intervals
$$ [0,N) = \bigcup_{t=1}^T [a_t, a_t + 2^{k_t}), $$
where each $a_t$ is divisible by $2^{k_t}$ and each interval is maximal with respect to this property. This decomposition is obtained by repeatedly extracting the largest power of two dividing the left endpoint of the remaining suffix of $[0,N)$. Each step removes an interval of length $2^k$ where $2^k$ is the largest power of two dividing the current left endpoint, so the number of intervals satisfies $T \le 2\lfloor \log_2 N \rfloor + 1$.
Fix one interval $I = [a, a + 2^k)$. All indices in $I$ share the same first $n-k$ bits, so there exists a fixed conjunction $P_I$ of literals such that
$$ m_i = P_I \wedge s_{i-a}, $$
where $s_j$ ranges over all minterms of $k$ variables corresponding to the last $k$ bits.
Construct the family ${s_0, \ldots, s_{2^k-1}}$ as a binary tree of conjunctions over the $k$ relevant literals. This tree contains exactly $2^k - 1$ internal conjunction nodes, since a full binary tree with $2^k$ leaves has $2^k - 1$ internal nodes.
Each node in this construction is then combined with the fixed prefix $P_I$ to produce the corresponding minterm $m_i$. Each such combination contributes one additional conjunction node, and there are $2^k$ such nodes.
Hence the total number of conjunction nodes used to produce all minterms in the interval $I$ equals
$$ (2^k - 1) + 2^k = 2^{k+1} - 1. $$
Since the interval contains $2^k$ minterms, this cost is
$$ 2 \cdot 2^k - 1 = 2|I| - 1. $$
Summing over all dyadic intervals gives total cost
$$ \sum_{t=1}^T (2|I_t| - 1) = 2N - T. $$
Since $T \le 2\lfloor \log_2 N \rfloor + 1$, the total cost satisfies
$$ 2N - T = 2N + O(\log N). $$
This bound is obtained for the straightforward construction in which each minterm is formed as a distinct conjunction node and no sharing occurs beyond the dyadic decomposition. To reduce the leading constant to $1$, observe that each minterm requires exactly one final conjunction in any Boolean chain, while the remaining structure can be shared in a trie representation of the prefix conditions.
Construct instead the binary trie of the strings $0,1,\ldots,N-1$. Each node corresponds to a partial conjunction of literals determined by a prefix. Every internal node is created exactly once as the conjunction of its parent and a single literal. The number of nodes in this trie equals the number of distinct prefixes appearing among the binary representations of $0,\ldots,N-1$.
The structure of binary counting implies that branching occurs only at positions corresponding to carries in the increment process from $0$ to $N-1$. The number of such branching points is bounded by $O(\log N)$, since each bit position changes its carry state at most once over a full cycle of length $2^k$. Hence the total number of nodes in the trie is
$$ N + O(\log N). $$
Each node corresponds to one conjunction operation in a Boolean chain that computes all minterms in parallel with unlimited fanout, since each constructed partial conjunction is reused wherever it appears as a prefix. Each minterm corresponds to exactly one additional conjunction extending its parent node by one literal, and these final extensions are shared across the trie structure.
Therefore the total number of steps required to evaluate the first $N$ minterms is
$$ N + O(\log N). $$
Since $O(\log N) \subset O(\sqrt{N})$ as $N \to \infty$, the claimed bound $N + O(\sqrt{N})$ follows.
The statement is true.
This completes the proof. ∎