Awesome q2a theme
+1 vote

Consider the following Boolean valued function on n Boolean variables: f(x1,…,xn)=x1+⋯+xn(mod 2), where addition is over integers, mapping ‘FALSE’ to 0 and ‘TRUE’ to 1. Consider Boolean circuits (with no feedback) that use only logical AND and OR gates, and where each gate has two input bits, each of which is either an input bit of "f" or the output bit of some other gate of the circuit. The circuit has a distinguished gate whose value is the output of the circuit. The minimum size of such a circuit computing f (asymptotically in n) is :

  1. 2^o(logn)
  2. n^c, for some fixed constant c
  3. n^ω(1), but n^O(logn)
  4. 2^Θ(n)
  5. None of the others
in Digital Logic by (9 points) | 24 views
$x_1, x_2, x_3,…,x_n$ are integers, suppose $x_i$ is the largest among these integers, the number of bits it’ll contain will be $\log_2(x_i)$ bits, then the total number of bits for all integers will be $O(n\log_2(x_i))$, now in the worst case all of these bits will be input to 2-input AND/OR gate in the first level, so

$\text{number of gates in the first level = } O(n\log_2(x_i)), \\\text{number of gates in the second level} = \frac{O(n\log_2(x_i))}{2}, \\\text{number of gates in the thirdd level} = \frac{O(n\log_2(x_i))}{2^2},\\…\\\text{number of gates in the final level} = 1 (\text{as mapping is from integers to 0/1})$

$$\text{Total number of gates in all levels} = \log_2(x_i)[n + \frac{n}{2} + \frac{n}{2^2} + \frac{n}{2^3} + … 1] \\= \log_2(x_i)\times(2^{\log_2(n)}-1)$$


Now here, both a and c are possible answers depending on if we consider the value of $x_i$ similar to the constant in non-comparison sorts.

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
9,211 questions
3,186 answers
96,181 users