# Prove that exists PARITYn fuction with size O(n^2)

Have to find Boolean circuit formula that solves PARITYn problem with complexity O(n^2)?

(Function PARITYn(x1, . . . , xn) is equal to 1 if and only if the number of variables x1, . . . , xn equal to 1 is odd.)

• What did you try? Where did you get stuck? What's the smallest circuit you've been able to design so far? Do you know how to compute the sum with a circuit of size $O(n^2)$? We're happy to help you understand the concepts but just solving exercise-style problems for you is unlikely to achieve that. You might find this page helpful in improving your question. – D.W. Feb 20 at 23:17
• Use divide and conquer. – Yuval Filmus Feb 23 at 1:55