We shall now devote our time to answering the question about worst case of Boolean function for its computation with circuits. Suppose that we are given a Boolean function of fixed number of variables, so some f of x_1 through x_n. Now, what can be the largest amount of elements, largest amount of keys that we'll actually need to build a circuit that computes this function? Now this is a question of worst case which is very similar to the questions that were asked for algorithms, say, sorting algorithms or other algorithms in standard introductory courses, like, what's the worst-case performance of algorithms? That's the same question here. What's the worst-case performance of our computation model of circuits? How large circuits do we sometimes need? How will we solve this question? We'll get two bounds: the lower bound, the upper bound. The upper bound would be provided by a procedure that allows us to take a function and algorithmically construct a circuit that computes this function. We'll learn about it later. But we'll start with the lower bound. If we have a function of n variables, then we'll prove that sometimes for some functions of this sort we'll need at least the circuits of size 2_n divided by n. Well, multiplied by some constant maybe. The bound that we'll obtain would be at least this one: 1 over 100 times 2_n over n. So the order of growth is this one. The lower bound that we'll prove is based on the standard cardinality-based argument. Imagine that we have circuits all the circuits of this size. Well, not exceeding this size. Suppose that we have constructed the set of all circuits of small size. Now suppose that we have the set of all Boolean functions, if we assume that circuits are of one output each, then every circuit computes some function. Clearly, different functions. They are computed by different circuits. This computability relation is an injection here. So different functions, they are computed by different circuits. Well, of course, there are sometimes multiple ways to compute the same function, so really we'll have this kind of relation, but it's still an injection; we cannot have two different functions here that are computed by the same circuit. Now we cannot have this kind of situation here. Thus, if all functions were computable by circuits of this size, then clearly, we would have the inequality that the number of all the functions, 2_2_n, will not exceed the number of circuits. On the other hand, if we prove a different inequality, if we prove that the number of circuits is less than 2_2_n, well, clearly, you have a corollary that there exists some function and actually lots of them that cannot be computed by such small circuits. We'll just not have enough circuits to compute all the functions. Now we'll prove this inequality. To prove it actually we have to bound somehow the number of circuits of bounded size. This is what we'll do next. Let's first count not the circuits, but trees. Assume that we have a tree, which is ordered and directed so that we have a root of the tree. We'll mark it with red. Then the tree is a binary, so each vertex has at most two predecessors in this tree. Let's fix the number of edges in the tree. Let the number of edges be given and equal to m. The fact that the tree is ordered means that for each vertex, we know what is the left sub-tree of this vertex and what is the right sub-tree of this vertex. If we actually embed a tree on the plane so that we draw this tree and the plane. This is one of the ways in which we can fix the order. We now know what is the left sub-tree of a vertex and what is the right sub-tree of a vertex. Now let's provide a way to encode this tree. This is done by depth-first traversal. A depth-first traversal is a way to traversal the tree where we starts at the root of the tree. Hence, we now go closer to the leaves of the tree. First, prioritizing the left subtree, then the right subtree, and each time we can go further from the root, we go on. If we cannot go further, then we backtrack, go closer to the root. We first go here, then here, then we'd have to backtrack. Then we can go further from the root, further, further and further. Then we go back. Then we can get here, then we have to go back. Then we should go up, then go down, go up, and then finally down. This looks a lot like going round the castle, going round some wall. If it were a great Chinese wall, but it looked like a Bonsai tree, then this would be our way of traversing, so going around this wall. What this depth-first reversal allows us to do? It allows us to write the code for this tree. Each time we go further from the root, we write zero. Each time we get closer to the root, we write one. Let's now provide the code for this tree. We first go up and up here, so we write two zeros. Then we have to go down, down this edge, so we write one. Then we go up and up and up and up. Then we have to go three times down, and we're now at this vertex. Then we go up, and then we have to go down three times, down, down, down. Then we get up and up, then down, up and down, down. What we see about this code is that the number of zeros is equal to the number of ones for this code, and actually, if we take any prefix of this code, then the number of ones would be, at most, equal to the number of zeros. We cannot go down further than we went up. This actually corresponds to balanced parenthesis sequence, but we don't really need that. [inaudible] that's currently just to be able to write a bound for the number of trees. We need to find the length of this whole sequence. In our traversal, for every edge of our tree, we went ones up the edge and then down the edge, and so the number of the zeros and ones in the sequence is 2m. The number of trees does not exceed the number of all sequences of zeros and ones of length 2m, and so the number of trees with m edges does not exceed 2_2m, that's 4_m. What we need to see here, well, to believe in this bound, is that every code can be decoded. But if we now say erase this tree, then we can easily reconstruct this tree by using this code, so we start and then we go up and up, and then we go down, and we're now in this vertex. Then we go up and up and up and up. Then we go three times down, and we are in this vertex. Then we go up and then we go three times down, so we're now back in the root. Then we go up and up, then down and we are here, and then we go up, and finally, two times down. We now have decoded the tree, and this tree is actually the same order three that we had before prior to writing this code. Really, the relation between the trees and their codes is such that to every tree, there corresponds a code, and the tree can be decoded. Of course, there are some sequences of zeros and ones that are not valid codes of any trees. But then, we just have an inequality here, not a pure equality. For now, we learned that the number of trees with m edges can be bounded like this. They're trees in which sub trees are ordered. Actually, suppose that we do not just have tree, but we have L tree with the vertices marked as IDs, so we have a canonical order of the vertices, when we deconstruct a tree into a code and then decode this tree, we can label the vertices with numbers that correspond to the time we first encounter this vertex. This is the first vertex, this is the second, this is the third. Then we get back to second. This is the fourth, the fifth, the sixth, the seventh. This is the eighth. This is the ninth, 10th, and 11th. You see that really such code gives rise to tree with some canonical labeling of its vertices. Now, let's see how we can get from trees to circuits.