A

Admin • 832.70K Points
Coach

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)

Explanation by: Admin

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.

You must be Logged in to update hint/solution

Discusssion

Login to discuss.

Be the first to start discuss.