Consider a Boolean function of ‘n’ variables. The order of an algorithm that…
2018
Consider a Boolean function of ‘n’ variables. The order of an algorithm that determines whether the Boolean function produces a output 1 is :
- A.
Logarithmic
- B.
Linear
- C.
Quadratic
- D.
Exponential
Attempted by 175 students.
Show answer & explanation
Correct answer: D
Final answer: Exponential (Θ(2^n)).
Explanation: To determine whether a Boolean function of n variables ever outputs 1, you must consider assignments to all n variables. The total number of possible input assignments is 2^n.
A simple algorithm evaluates the function on each possible assignment until it finds an assignment that yields 1, or until all assignments have been checked.
In the worst case (when no assignment yields 1), the algorithm must evaluate the function on all 2^n assignments.
Therefore the worst-case time complexity is Θ(2^n), which is exponential in n. Any claimed algorithm with logarithmic, linear, or quadratic time in n would not examine all assignments and so cannot guarantee correctness in the worst case.
Note: This reasoning assumes a general Boolean function with no additional structure or shortcuts. Specialized representations or additional information could allow faster algorithms in specific cases, but for an arbitrary Boolean function the worst-case complexity is exponential.