UGC NET Computer Science July 2018 - II Question 30
Question 30
30. Consider a Boolean function of ‘n’ variables. The order of an algorithm that determines whether the Boolean function produces a output 1 is :
Options:
(1) Logarithmic
(2) Linear
(3) Quadratic
(4) Exponential
Answer : (4) Exponential
Explanation Question 30
Given:
Boolean function has input which has ‘n’ variables
Boolean function has output 1
Find complexity of given boolean function ?
Given function is boolean function so, it takes "n" variable input which are boolean having either value 1 or 0. Each variable in input set have 2 choices and we have “n” such variables in input set.
So, total number of choices we get maximum is 2n.
It means exponential.
Given:
Boolean function has input which has ‘n’ variables
Boolean function has output 1
Find complexity of given boolean function ?
Given function is boolean function so, it takes "n" variable input which are boolean having either value 1 or 0. Each variable in input set have 2 choices and we have “n” such variables in input set.
So, total number of choices we get maximum is 2n.
It means exponential.
So, Option (4) is correct answer.