Convert conjunctive normal form to equivalent boolean formula with only NAND gates
Yes, it can be converted to such a formula of size $O(n)$ (i.e., only a constant-factor increase in formula size).  The conversion simply recursively applies the following rules:

$$\begin{align*}
\neg a &amp;\equiv NAND(a,\text{True})\\
a \lor b &amp;\equiv NAND(\neg a, \neg b)\\
a \land b &amp;\equiv \neg NAND(a,b)
\end{align*}$$

It is easy to check that the resulting formula has linear size.

For instance, the clause $x_1 \lor \neg x_2 \lor \neg x_3$ represents $(x_1 \lor \neg x_2) \lor \neg x_3$, so applying the above rules we obtain the boolean formula

$$NAND(NAND(NAND(NAND(x_1,\text{True}),x_2),\text{True}),x_3).$$

In this way, each clause can be converted to a boolean formula of size $O(1)$.  All that remains is to convert the conjunction of these clauses, and that can be done by expressing $c_1 \land \cdots \land c_m$ as $((c_1 \land c_2) \land \cdots) \land c_m$ and then applying the rule for $a \land b$ repeatedly.