There is a basic result in circuit complexity that says:There exists a language that cannot be solved with circuits of size $o(\frac{2^n}{n})$.The argument is a simple counting argument on the number of boolean functions and the number of distinct circuits.  See, for example, these lecture notes.I believe it is unknown whether or not this bound is tight.  That is, we don't know if the following statement is true:Every language can be solved with circuits of size $O(\frac{2^n}{n})$.If this statement were true, would it have any interesting implications for complexity theory?
Implications of the $\Omega(\frac{2^n}{n})$ circuit lower bound being tight
complexity theory;lower bounds;circuits
This has been proved by Muller as early as 1956. Here is the construction. Let $k$ be a parameter. We first compute all possible functions on the first $k$ inputs in size $O(2^{2^k})$ (see below). We then construct a decision tree for the other $n-k$ variables, connecting it to the correct function on the remaining variables. This takes $O(2^{n-k})$ (see below), for a total of $O(2^{2^k}) + O(2^{n-k})$. Choosing $k = \log (n - \log n)$, we obtain the desired bound.We compute all possible functions on $k$ inputs inductively. Let $Z_k$ be the size of a circuit computing all possible functions on $k$ inputs. There are two functions on zero inputs, so $Z_0 = 2$. Every function $f(x_1,\ldots,x_k)$ on $k$ inputs can be written as $x_k f(x_1,\ldots,x_{k-1},1) + \overline{x_k} f(x_1,\ldots,x_{k-1},0)$, so $Z_k = Z_{k-1} + 2^{2^k} \cdot O(1)$. The solution of this recurrence is $Z_k = O(2^{2^k})$.In order to compute the decision tree, we use a similar construction: given a tree $T$ for the first $k-1$ variables, we can construct a tree for the first $k$ variables of the form $x_k T + \overline{x_k} T$. The recurrence we get is $W_k = 2W_{k-1} + O(1)$, whose solution is $W_k = O(2^k)$.