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)
AnswerD.
O(sum + n)
Answer: Option C
Solution
Answer: Option C
No explanation is given for this question Let's Discuss on Board