1

We need to find out the maximum no-adjacent subset-sum in the given array,

no-adjacent: we cannot pick adjacent elements while forming the maximum subset-sum.

For example:

arr = [5, 3, 7, 14]

Solution : [5, 14] : 19 maximum sum

Explanation:

5 and 14 are not adjacent numbers and their sum is maximum.

Code

int main(){

   //input
   int n;
   cin>>n;
   vector<int> arr;
   while(n--){
      int x;
      cin>>x;
      arr.push_back(x);
   }

   int max_adj = INT32_MIN;

   for (int i = 0; i < arr.size(); i++)
      max_adj = max(max_adj, maxSum(arr, i));

 }


int maxSum(vector<int> &arr, int vidx) {

   if (vidx >= arr.size()) {
       return 0;
   }

   int max_ = 0;

   for (int i = vidx + 2; i < arr.size(); i++) {
       max_ = max(max_, maxSum(arr, i));
   }

   return max_ + arr[vidx];
}

The above approach is a brute force/naive recursive approach to solve this problem. I know there exists a better dp solution.

But, I am just looking for a way how to find out the

Big O time complexity

of this recursive solution mathematically.

tusharRawat
  • 719
  • 10
  • 24
  • No, I guess, https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it solution to this question explains Big O in a very broad general scenario where master's theorem is applicable, but this question involves some specific way to derive time complexity. – tusharRawat Mar 11 '20 at 18:04
  • If you want specific help in deriving the time complexity bounds of your shown algorithm, I suggest that you clarify that in your question and add an explanation of your attempts to solve this up to now and where you are stuck. The way the question is worded now "*I am just looking for a way how to find*", without any further attempt, suggests to me that you were looking for generic methods, which are given by the four linked duplicates (including specific ones for recursive functions). – walnut Mar 11 '20 at 18:16

0 Answers0