# Computing parity function on n variables with O(n) gates

Sipser example 9.29

He says: "one way to do so (compute the parity function with O(n) gates. One way to do so is build a binary tree that computes the XOR function, where the XOR function is the same as parity on 2 variables, and then implement each XOR gate with two NOTs and two ANDs, and one OR. ... Let A be the language of strings that contain an odd number of 1's. Then A has circuit complexity O(n)."

I'm not seeing the steps that lead to saying that A has circuit complexity of O(n). Why can we say that if we implement a binary tree of XORs we can compute the parity with O(n) gates?

Because the parity is 1 if and only if the XOR of all the bits is 1. In other words, computing the parity is equivalent to computing the XOR of the bits. Sipser describes how to compute the XOR of the $n$ bits with $O(n)$ gates, which means that this same circuit computes the parity of those $n$ bits with $O(n)$ gates.
• @lars, you quoted it in your question. You build a binary tree that computes the XOR function. The binary tree has $n$ leaves, one leaf per input, and each internal node in the tree is an XOR gate. The root of the tree holds the output. There are $n$ leaves and $O(n)$ internal nodes, so a total of $O(n)$ XOR gates. The part you excluded also explains that each XOR gate can be implemented with $O(1)$ NOT/OR/AND gates, so in total, it takes $O(1) \times O(n) = O(n)$ gates to compute the XOR of the $n$ bits. – D.W. Nov 17 '13 at 18:03