Register

UGC NET CSE | July 2018 | Part 2 | Question: 30

• edited by
2,989 views
0 0 votes

Consider a Boolean function of 'n' variables. The order of an algorithm that determines whether the Boolean function produces a output 1 is

  1. Logarithmic
  2. Linear
  3. Quadratic
  4. Exponential

2 Answers

7 7 votes

N boolean variable ===> 2n rows in truth table.

for saying o/p 1 for the given function, in worst case it needs to check every possible row ===> O(2n) ===> Exponential

 

Option D is correct

2 2 votes

N boolean variables will result in 2n  output variables in the truth table. 

In order to determine whether an output 1 is resulted, in the worst case(by brute force), the algo needs to check all possible outputs (2n) which implies an exponential algo 

 

Voting & Accepting an answer helps improve the community
Answer:
← Previous · UGC NET CSE | July 2...Next → · UGC NET CSE | July 2...
← Previous in category · Time Complexity for ...Next in category → · UGC NET CSE | July 2...
Position:
Show:

Related questions

0 0 votes
4 4 answers
3.7k
3.7k views
Pooja Khatri asked Jul 13, 2018
3,673 views
UGC NET CSE | July 2018 | Part 2 | Question: 21
The solution of the recurrence relation $T(m) = T(3m/4)+1$ is$\Theta (\lg \: m)$$\Theta (m)$$\Theta (m\lg m)$$\Theta (\lg\lg m)$
1 1 vote
1 1 answer
3.1k
3.1k views
Pooja Khatri asked Jul 13, 2018
3,120 views
UGC NET CSE | July 2018 | Part 2 | Question: 27
Match the following with respect to algorithm paradigms :$\begin{array}{clcl} & \textbf{List-I} & {} & \textbf{List-II} \\ \text{(a)} & \text{The 8-Queen's problem} & \t...
1 1 vote
2 2 answers
3.4k
3.4k views
Pooja Khatri asked Jul 13, 2018
3,423 views
UGC NET CSE | July 2018 | Part 2 | Question: 2
The definitions in an XML document are said to be ______ when the tagging system ans definitions in the DTD are all in compliancewell-formedreasonablevalidlogical
1 1 vote
1 1 answer
4.5k
4.5k views
Pooja Khatri asked Jul 13, 2018
4,490 views
UGC NET CSE | July 2018 | Part 2 | Question: 1
Consider the JavaScript Code:var y=”12” function f() { var y=”6”; alert (this.y); function g() {alert (y); } g(); } f();If $M$ is the number of alert dialog boxes generat...