GATE Exam | Aptitude Questions | GATE Syllabus | GATE Result | Mock Test | GATE Preparation
0 votes
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]);

asked in Algorithm design techniques: greedy, dynamic programming and divide‐and‐conquer by gate

1 Answer

0 votes
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)
answered by gate

Related questions

The best answer to any question