CODEWITHSUNDEEP
javaalgorithmrecursionasymptotic-complexityrecurrence
Balboa
Balboa

Reputation: 59

Cost of a java method with multiple recursion

We have the following Java method:

static void comb(int[] a, int i, int max) {
    if(i < 0) {
        for(int h = 0; h < a.length; h++)
            System.out.print((char)(’a’+a[h]));
        System.out.print("\n");
        return;
    }
    for(int v = max; v >= i; v--) {
        a[i] = v;
        comb(a, i-1, v-1);
    }
}

static void comb(int[] a, int n) { // a.length <= n
    comb(a, a.length-1, n - 1);
    return;
}

I have to determine an asymptotic estimate of the cost of the algorithm comb(int[],int) in function of the size of the input. Since I'm just starting out with this type of exercises, I can not understand if in this case for input size means the size of the array a or some other method parameter. Once identified the input size, how to proceed to determine the cost of having a multiple recursion?

Please, you can tell me the recurrence equation which determines the cost?

Upvotes: 1

Views: 1025

Answers (3)

Mikhailov Valentin
Mikhailov Valentin

Reputation: 1102

To determine the complexity of this algorithm you have to understand on which "work" you spend most of the time. Different kind of algorithm may depend different aspects of its parameters like input size, input type, input order, and so on. This one depends on array size and n.

Operations like System.out.print, (char), 'a' + a [h], a.length, h++ and so on are constant time operations and mostly depends on processor commands you will get after compilation and from a processor on which you will execute those instructions. But eventually they can be summed to constant say C. This constant will not depend on the algorithm and input size so you can safely omit it from estimation.

This algorithm has linearly dependent on the input size because it cycles, it's input array (with a cycle from h = 0 to last array element). And because n can be equal to array size (a.length = n - this is the worst case for this algorithm because it forces it execute recursion "array size" times) we should consider this input case in our estimation. And then we get another cycle with recursion which will execute method comb other n times.

So in the worst case we will get a O(n*n*C) number of execution steps for significantly large input size constant C will become insignificant so you can omit it from estimation. Thus final estimation will be O(n^2).

Upvotes: 1

Eran
Eran

Reputation: 393781

The original method being called is comb(int[] a, int n), and you know that a.length <= n. This means you can bound the running time of the method with a function of n, but you should think whether you can compute a better bound with a function of both n and a.length.

For example, if the method executes a.length * n steps and each step takes a constant amount of time, you can say that the method takes O(n^2) time, but O(a.length * n) would be more accurate (especially if n is much larger than a.length.

You should analyze how many times the method is called recursively, and how many operations occur in each call.

Upvotes: 1

Neil Masson
Neil Masson

Reputation: 2689

Basically for a given size of input array, how many steps does it take to compute the answer? If you double the input size, what happens to the number of steps? The key is to examine your loops and work out how many times they get executed.

Upvotes: 0

Related Questions