Question

Which of the following is true about the time complexity of the recursive solution of set partition problem?

(a) It has an exponential time complexity

(b) It has a linear time complexity

(c) It has a logarithmic time complexity

(d) it has a time complexity of O(n2)

This question was posed to me by my school teacher while I was bunking the class.

The above asked question is from Checksum, Complexity Classes & NP Complete Problems topic in section Checksum, Complexity Classes & NP Complete Problems of Data Structures & Algorithms II

Answer 1

The correct choice is (a) It has an exponential time complexity

The explanation is: Set partition problem has both recursive as well as dynamic programming solution. The recursive solution has an exponential time complexity as it will require to check for all subsets in the worst case.