CODEWITHSUNDEEP
recursionbig-otime-complexity
TheLipster
TheLipster

Reputation: 33

Worst Case Running time

I have the following Code Fragment:

public static boolean sumSearch(int[] a, int n, int x) {
    if (n == 0) {
         return ( x==0 );
    }
    return (sumSearch(a, n-1, x-a[n-1]) || sumSearch(a, n-1, x));

So from what I gather... does the third parameter even matter? Since return x==0 doesn't matter for the worst case, it would be O(n) calls since n-1 is done so the worst time complexity can only be O(n)? Is this the correct line of thinking?

Upvotes: 0

Views: 96

Answers (1)

IllusiveBrian
IllusiveBrian

Reputation: 3234

Well, considering this type of problem is NP-Complete, I think we can rule out a time complexity of O(n). I think this algorithm has a worst case time of O(2^n). If you imagine the calls like a tree, each "level" of the tree has twice as many calls as the level before it, which of course comes out to O(2^n).

Upvotes: 1

Related Questions