Question

What is the worst case time complexity of dynamic programming solution of set partition problem(sum=sum of set elements)?

(a) O(n)

(b) O(sum)

(c) O(n^2)

(d) O(sum*n)

The question was posed to me in an interview.

This intriguing question originated from Checksum, Complexity Classes & NP Complete Problems in division Checksum, Complexity Classes & NP Complete Problems of Data Structures & Algorithms II

Answer 1

Right choice is (d) O(sum*n)

To explain: Set partition problem has both recursive as well as dynamic programming solution. The dynamic programming solution has a time complexity of O(n*sum) as it as a nested loop with limits from 1 to n and 1 to sum respectively.