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?

Answer 1

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