CODEWITHSUNDEEP
c++algorithmbig-o
idealistikz
idealistikz

Reputation: 1267

Divide and Conquer Algorithm Running Time

I am having trouble determining the running time of the following algorithm.

bool IsMeasurable(int target, vector<int> & weights, int index) {
    if (target == 0) return true;
    if (index >= weights.size()) return false;
    return (IsMeasurable(target-weights[index],weights,index+1) ||
            IsMeasurable(target+weights[index],weights,index+1) ||
            IsMeasurable(target,weights,index+1));
 }

bool IsMeasurable(int target, vector<int> & weights) {
    return IsMeasurable(target,weights,0);
}

The function determines whether it can measure a given target weight given a vector of weights. We start with the first item in the vector and recursively call functions adding, subtracting, and leaving alone the current item with the target weight.

I know it takes O(n) time to go through the vector, but how do I consider the recursive calls to determine the running time?

Upvotes: 0

Views: 179

Answers (1)

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

At each recursion index is incremented by 1. Also, it gets divided into three recursive calls.

Hence the worst case time complexity shall be O(3^N) where N is the size of the vector.

You can view the recursive calls as a tree where each node gets branched out to three nodes at each step.

1
1 1 1
111 111 111
..

Upvotes: 3

Related Questions