What is the worst case time complexity of following implementation of subset sum problem.
// Returns true if there is a subset of set[] with sun equal to given sum bool isSubsetSum(int set[], int n, int sum) { // Base Cases if (sum == 0) return true; if (n == 0 && sum != 0) return false; // If last element is greater than sum, then ignore it if (set[n-1] > sum) return isSubsetSum(set, n-1, sum); /* else, check if sum can be obtained by any of the following (a) including the last element (b) excluding the last element */ return isSubsetSum(set, n-1, sum) || isSubsetSum(set, n-1, sum-set[n-1]); } |
(A) O(n * 2^n)
(B) O(n^2)
(C) O(n^2 * 2^n)
(D) O(2^n)
Answer: (D)
Explanation: Following is the recurrence for given implementation of subset sum problem
T(n) = 2T(n-1) + C1
T(0) = C1
Where C1 and C2 are some machine specific constants.
The solution of recurrence is O(2^n)
We can see it with the help of recurrence tree method
C1
/ \
T(n-1) T(n-1)
C1
/ \
C1 C1
/ \ / \
T(n-2) T(n-2) T(n-2) T(n-2)
C1
/ \
C1 C1
/ \ / \
C1 C1 C1 C1
/ \ / \ / \ / \
If we sum the above tree level by level, we get the following series
T(n) = C1 + 2C1 + 4C1 + 8C1 + ...
The above series is Geometrical progression and there will be n terms in it.
So T(n) = O(2^n)
Whether you’re preparing for your first job interview or aiming to upskill in this ever-evolving tech landscape, neveropen Courses are your key to success. We provide top-quality content at affordable prices, all geared towards accelerating your growth in a time-bound manner. Join the millions we’ve already empowered, and we’re here to do the same for you. Don’t miss out – check it out now!
