Define the function majorityn : {0,1}n → {0,1} as

 

Thus, the majorityn function returns the majority vote of the inputs. Show that majorityn can be computed with:

a. O(n²) size circuits.

b. O(n log n) size circuits. Recursively divide the number of inputs in half and use the result of Problem 9.23.

Problem 9.23.

Recall that you may consider circuits that output strings over {0,1} by designating several output gates. Let add_n : {0,1}²ⁿ → {0,1}ⁿ⁺¹ take two n bit binary integers and produce the n+1 bit sum. Show that you can compute the add_n function with O(n) size circuits.

Jo Eai < n/2; 1 ri 2 n/2. majority , (, . . , n)