Register

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

• edited by
2,007 views
0 votes
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
• edited by
User Avatar

2 Answers

7 votes
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

User Avatar
2 votes
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 

 

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
4 answers
1
Pooja Khatri asked Jul 13, 2018
2,185 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)$
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)$
User Avatar
0 votes
0 votes
1 answer
2
Pooja Khatri asked Jul 13, 2018
2,395 views
UGC NET CSE | July 2018 | Part 2 | Question: 27
Match the following with respect to algorithm paradigms : ... $\text{(a)-(iv), (b)-(iii), (c)-(ii), (d)-(i)}$
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...
User Avatar
1 votes
1 votes
2 answers
3
Pooja Khatri asked Jul 13, 2018
2,690 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 compliance well-formed reasonable valid logical
The definitions in an XML document are said to be ______ when the tagging system ans definitions in the DTD are all in compliancewell-formedreasonablevalidlogical
User Avatar
Link Copied!