# How to bound the size of Boolean circuits?

Every function $$f\colon \{ 0, 1 \}^n \to \{ 0, 1 \}$$ can be computed by a circuit over the standard unbounded fan-in basis $$\mathcal{B}_1 = \{ \neg, (\vee^n)_{n \in \mathbb{N}}, (\wedge^n)_{n \in \mathbb{N}} \}$$ of depth $$3$$ and size $$\mathcal{O}(2^n)$$ via the disjunctive or conjunctive normal form. Now, we can transform each circuit over $$\mathcal{B}_1$$ into a circuit over the standard bounded fan-in basis $$\mathcal{B}_0 = \{ \neg, \vee, \wedge \}$$ by substituting a gate of fan-in $$k$$ by a circuit of depth $$\mathcal{O}(\log k)$$ and size $$\mathcal{O}(k)$$ and, since each gate of the original circuit has a fan-in smaller than $$\mathcal{O}(2^n)$$, we get a circuit of depth $$\mathcal{O}(n)$$ and size $$\mathcal{O}(2^{2n})$$. How does http://www.cs.umd.edu/~jkatz/complexity/f05/lecture4.pdf obtain a size bounded by $$\mathcal{O}(n \cdot 2^n)$$?

Every function can be computed by a CNF (or a DNF). A CNF is the conjunction of up to $$2^n$$ clauses. Each clause involves up to $$n$$ variables. You can express each clause using a circuit of size $$O(n)$$, and the entire CNF using a circuit of size $$O(n 2^n)$$. In fact, this constructs a formula of size $$O(n2^n)$$.
The conversion from $$\mathcal{B}_1$$ to $$\mathcal{B}_0$$ doesn't increase the number of leaves in the circuit, and only increases the number of wires by a constant factor. It could increase the number of gates by an unbounded amount: for example, a fan-in $$k$$ AND gates translates to $$k-1$$ fan-in $$2$$ AND gates.
Lupanov improved the above bound to $$O(2^n/n)$$, which is tight due to a counting argument; see for example lecture notes of Jayalal Sarma. In the case of formulas, the tight bound is $$O(2^n/\log n)$$.