TAOCP 7.1.4 Exercise 117

Exercise 117. [M20] [M20] Compare Q(f) to B(f) when f = Mm(x1, . . . , xm; xm+1, . . . , xm+2m).

Verified: no
Solve time: 4m59s

Solution

Let $f = M_m(x_1,\ldots,x_m; x_{m+1},\ldots,x_{2m})$, where $M_m$ denotes the equality function on two $m$-bit blocks, so that $f=1$ if and only if $x_i = x_{m+i}$ for all $1 \le i \le m$.

For a BDD of $f$, a node at level $k$ corresponds to a subfunction determined by the first $k$ comparisons $x_i = x_{m+i}$, $1 \le i \le k$. Such a subfunction is completely determined by the set of indices where equality has already been forced and the remaining unconstrained suffix. The only relevant state after $k$ steps is whether all previous equalities hold, since any mismatch forces the function to $\bot$ permanently.

Thus, at level $k$ there are exactly $k+1$ distinct reachable subfunctions: one state corresponds to the “still consistent with equality” case, and each earlier mismatch position produces a distinct dead configuration that propagates to $\bot$ but remains distinct in the reduced ordered representation until merging occurs at sinks. This yields a linear growth of distinct beads per level up to level $m$.

After all $m$ comparisons, the remaining subfunctions are constants: one yielding $\top$ (complete equality preserved) and one yielding $\bot$ (a mismatch has occurred). Hence the last level contributes only sink structure.

Therefore the quasi-profile $Q(f)$ is

$$ Q(f) = (1,2,3,\ldots,m+1,m,\ldots,2,1), $$

where the sequence increases by $1$ per level up to $m+1$ and then decreases symmetrically as the remaining unconstrained structure collapses toward sinks under reduction.

The size of the BDD satisfies $B(f) = \sum Q(f)$, since each bead corresponds to exactly one node. Hence

$$ B(f) = \left(\sum_{k=1}^{m} (k+1)\right) + \left(\sum_{k=1}^{m-1} (k+1)\right) + 2, $$

where the final $2$ accounts for the sink nodes $\bot$ and $\top$.

Evaluating the sums,

$$ \sum_{k=1}^{m} (k+1) = \frac{m(m+1)}{2} + m = \frac{m^2+3m}{2}, $$

and

$$ \sum_{k=1}^{m-1} (k+1) = \frac{(m-1)m}{2} + (m-1) = \frac{m^2+m-2}{2}. $$

Adding all contributions gives

$$ B(f) = \frac{m^2+3m}{2} + \frac{m^2+m-2}{2} + 2 = \frac{2m^2+4m}{2} = m^2 + 2m. $$

Hence the BDD size grows quadratically in $m$, while the quasi-profile is triangular and symmetric.

$$ \boxed{Q(f) = (1,2,\ldots,m+1,m,\ldots,2,1), \quad B(f) = m^2 + 2m.} $$