1

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?

Improve this question
3
  • If this is assignment it should be a part of the question what to use as input size. Or you can use both of your parameters simultaneously. Commented Dec 10, 2015 at 15:21
  • drawing the recursion tree would help Commented Dec 10, 2015 at 15:21
  • printing is very expensive, if you are printing to a file it about 100x more expensive than the rest of your code, but if you write to a DOS console it could be 10,000x more expensive. If you have an O(n^2) algo eventually it can be more expensive than printing but your problem has to be really big. Commented Dec 10, 2015 at 16:32

3 Answers 3

Reset to default
1

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).

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

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.

Improve this answer

1 Comment

thus in this case, since we have a recursion inside of a for, the cost is given by the number of recursive activations, multiplied by the number of times that is executed for? so how could I write the recurrence equation that allows me to calculate the cost?
0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.