# Can you compute a majority function of n-bits using an O(n) size circuit?

Are you able to construct a boolean circuit that computes the majority function of n bits where the circuit only takes up O(n) space? If so, what would that circuit look like?

I have a feeling it has to do with a Full Adder, but I am unsure.

Interpret each input as a 1-bit number, and sum all the inputs in a binary-tree fashion.

At the $$i$$-th level of the tree you're dealing with numbers with at most $$i+1$$ bits. Hence the number of gates on the generic $$i$$-th level is $$O(i \cdot \frac{n}{2^i})$$ and the overall number of gates is $$O\left( \sum_{i=1}^{\log n} i \frac{n}{2^i} \right) = O(n)$$.

Once you have found the sum of the inputs, simply compare it with $$\lfloor n/2 \rfloor +1$$.

• I think that makes sense - my last point of confusion would be in that final comparison. How would I perform that final comparison using logical gates? Nov 25, 2023 at 23:33
• Also, in the initial circuit - how does adding the individual bits pairwise result in shortening the number of bits to i + 1 - wouldn't each two bits result in a sum and carry bit? I might be misunderstanding what you're saying here Nov 25, 2023 at 23:40
• @circuitman324 You can just compare the bits of of the final sum with the bits of $\lfloor n/ 2 \rfloor +1$ one by one, from the most significant digit. As soon as one bit is $1$ while the other is $0$, the number with the $1$ bit is lager. This can be done with a constant number of gates per bit pair (you need to compare the current bit pair while remembering if a decision in which number is larger has already been made). See the Digital Comparator page on wikipedia. Nov 26, 2023 at 9:40
• Assume that $n$ is a power of $2$ (if it's not then the same argument applies with suitable rounding, the asymptotic side of the circuit is not affected). Adding the $n$ individual bits pairwise results in $n/2$ numbers with at most $2$ bits each. Adding these $2$-bit numbers pairwise results in $n/4$ numbers with at most $3$ bits each. In general, on the $i$-th level you add $n/2^{i-1}$ numbers with $i$ bits each and get $n/2^{i}$ numbers with $i+1$ bits each. Nov 26, 2023 at 9:40
• Thanks! I was also wondering - could you elaborate more on how to handle the case where n is not a power of 2? Nov 26, 2023 at 23:19