1. Computer Science Engineering (CSE)
  2. Design and Analysis of Algorithms
  3. What is the worst case time complexity o...
Q.

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(n2)
D. o(sum*n)
Answer» D. o(sum*n)
Explanation: 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.

Discussion