Q.

What will be the auxiliary space complexity of dynamic programming solution of set partition problem(sum=sum of set elements)?

A. o(n log n)
B. o(n2)
C. o(2n)
D. o(sum*n)
Answer» D. o(sum*n)
Explanation: the auxiliary space complexity of set partition problem is required in order to store the partition table. it takes up a space of n*sum, so its auxiliary space requirement becomes o(n*sum).
1.6k
0
Do you find this helpful?
3

Discussion

No comments yet