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

McqMate

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.

3.6k

0

Do you find this helpful?

27

View all MCQs in

Design and Analysis of Algorithms

Discussion

No comments yet

Related MCQs

What will be the auxiliary space complexity of dynamic programming solution of set partition problem(sum=sum of set elements)?
Recursive solution of Set partition problem is faster than dynamic problem solution in terms of time complexity.
Worst case is the worst case time complexity of Prim’s algorithm if adjacency matrix is used?
Recursive solution of subset sum problem is faster than dynamic problem solution in terms of time complexity.
Which of the following is true about the time complexity of the recursive solution of set partition problem?
You are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the time complexity of a dynamic programming implementation used to solve the coin change problem?
What is the time complexity of the above dynamic programming implementation of the assembly line scheduling problem?
What is the worst case time complexity of KMP algorithm for pattern searching (m = length of text, n = length of pattern)?
Rabin Karp algorithm and naive pattern searching algorithm have the same worst case time complexity.
What is the worst case time complexity of a quick sort algorithm?