Finding the time complexity of a recursive algorithm with a double for loop

Question

I am trying to find the tightest upper bound for the following upper bound. However, I am not able to get the correct answer. The algorithm is as follows:

public staticintrecursiveloopy(int n){
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            System.out.println("Hello.");
        }
    } if(n <= 2) {
        return 1;
    } else if(n % 2 == 0) {
        return(staticintrecursiveloopy(n+1));
    } else{
        return(staticintrecursiveloopy(n-2));
    }
}

I tried to draw out the recursion tree for this. I know that for each run of the algorithm the time complexity will be O(n²) plus the time taken for each of the recursive calls. Also, the recursion tree will have n levels. I then calculated the total time taken for each level:

For the first level, the time taken will be n². For the second level, since there are two recursive calls, the time taken will be 2n². For the third level, the time taken will be 4n ² and so on until n becomes <= 2.

Thus, the time complexity should be n² * (1 + 2 + 4 + .... + 2ⁿ). 1 + 2 + 4 + .... + 2ⁿ is a geometric sequence and its sum is equal to 2ⁿ - 1.Thus, the total time complexity should be O(2ⁿn²). However, the answer says O(n³). What am I doing wrong?

It's important to note that this recursion never branches, so you actually won't get multiple recursive calls occurring at some level. That's why the runtime works out to O(n^3), as @DebarghaRoy points out below, rather than something exponential. — templatetypedef
– templatetypedef, Commented Sep 24, 2020 at 5:10

Debargha Roy · Accepted Answer · 2020-09-24 05:07:37Z

Consider the below fragment

for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        System.out.println("Hello.");
    }
}

This doesn't need any introduction and is O(n²)

Now consider the below fragment

if(n <= 2) {
    return 1;
} else if(n % 2 == 0) {
    return(staticintrecursiveloopy(n+1));
} else {
    return(staticintrecursiveloopy(n-2));
}

How many times do you think this fragment will be executed?

If n%2 == 0 then the method staticintrecursiveloopy will be executed 1 extra time. Otherwise it goes about decresing it by 2, thus it'll be executed n/2 times (or (n+1)/2 if you include the other condition).

Thus the total number of times the method staticintrecursiveloopy will be executed is roughly n/2 which when expressed in terms of complexity becomes O(n).

And the method staticintrecursiveloopy calls a part with complexity O(n²) in each iteration, thus the total time complexity becomes

O(n) * O(n²) = O(n³).

Collectives™ on Stack Overflow

Finding the time complexity of a recursive algorithm with a double for loop

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related