What's the time complexity o() of this piece of code? java

Question

I think is O(3^n), any ideas? This method finds if a given number is a sum of any sub set of a given set(overoads boolean isSumOf(int[]s,int n)). The method cheks in every recursive call if the taget is equal to 0 or consumes the current number in the set (or not) and tries again, while target>0 and whie we haven't exhausted the array.

    * @param set a given set of natural numbers.
    * @param target the number. 
    * @param i where we are in the set.
    * @return true if we reached target, else returns false.
    **/
   private static boolean isSumOf(int[] set,int target,int i)
   {

        // Found the set if we are now at 0.
        boolean isSum = (target==0);
        // Look no further if no more to try.
        if ( target > 0 ) 
        {
            // Look no further if we've exhausted the array.
            if ( i < set.length )
            {
                // Try or consume this number in the set (or not) and try again.
                isSum = isSumOf(set, target - set[i], i)  // Consume the current number in the set and try again recursively. 
                    || isSumOf(set, target - set[i], i+1) // Consume the current number in the set and avdance to rhe next number.
                    || isSumOf(set, target, i+1); // Try the current number and avance to the next number in the set.
            }

        }

        return isSum;

Answer 1

Your problem is NP-complete. These are the bad news.

The good news is that it's a very well known NP-complete problem! Yey!

http://en.wikipedia.org/wiki/Subset_sum

Like said in a comment, your algorithm can run indefinitely, and will run for a very long time for even a moderate input size.

If you have any glimpse of hope for that code to run in a moderate size input, you need to rethink your approach.

One of the big problems in your approach is that you're calculating many duplicate sub-problems. Think of the usual naive Fibonnaci recursive implementation.

Your subproblems, on the bright side, have quite an optimal structure, which is a good indicator that your problem would be a great candidate for a Dynamic Programming approach. It makes things easier that you don't even need the exact numbers that sum up to the value, just a boolean output.

The wikipedia article I linked discusses some pseudo-polynomial approaches as well as a polynomial approach via Dynamic Programming.

Answer 2

It looks worse than O(3^n) because the first recursive call isSumOf(set, target - set[i], i) will call itself without advancing i, which for large targets will result in a huge amount of branching for each i.

A method like this can benefit from Memoization to reduce its complexity.