Vidyalelo
Data Structure · Q206

Dynamic Programming in Data Structures

Programming · Data Structure · question 206

Q206

What is the time complexity of the following dynamic programming implementation of the balanced partition problem where "n" is the number of elements and "sum" is their sum? #include int balanced_partition(int *arr, int len) int sm = 0, i, j; for(i = 0;i = arr[j - 1]) ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1]; return ans[sm/2][len]; int main() int arr[] = 3, 4, 5, 6, 7, 1, len = 6; int ans = balanced_partition(arr,len); if(ans == 0) printf("false"); else printf("true"); return 0;

A.
O(sum)
B.
O(n)
C.
O(sum * n)
Answer
D.
O(sum + n)

Answer: Option C

Solution

Answer: Option C
No explanation is given for this question Let's Discuss on Board