Question

What is the time complexity of the brute force algorithm used to solve the balanced partition problem?

(a) O(1)

(b) O(n)

(c) O(n^2)

(d) O(2^n)

This question was posed to me in a job interview.

This intriguing question originated from Balanced Partition topic in section Dynamic Programming of Data Structures & Algorithms II

Answer 1

Correct answer is (d) O(2^n)

For explanation: In the brute force implementation, all the possible subsets will be formed. This takes exponential time.