Should I consider whether an input value is even or odd when calculating time complexity?

Question

I have the following function:

def pascal_triangle(i:int,j:int):
    j = min(j, i-j + 1)
    if i == 1 or j == 1:
        return 1
    elif j > i or j == 0 or i < 1 or j < 1:
        return 0 
    else:
         return pascal_triangle(i-1,j-1) + pascal_triangle(i-1,j)

The input value for j has the following constraint:

1<=j<=i/2

My computation for the time complexity is as follows:

f(i,j) = f(i-1,j-1) + f(i-1,j) = f(i-n,j-n) + ... + f(i-n,j)

So, to find the max n, we have:

i-n>=1
j-n>=1
i-n>=j

and, since we know that:

j>=1
j<=i/2

The max n is i/2-1, so the time complexity is O(2^(i/2-1)), and the space complexity is the maximum depth of recursion(n) times needed space for each time(O(1)), O(2^*(i/2-1)).

I hope my calculation is correct. Now my concern is that if i is odd, This number is not divisible by 2, but the terms of function must be an integer. Therefore, I want to know should I write the time complexity like this:

The time complexity and space complexity of the function are both:

O(2^(i/2-1)) if i is even
O(2^(i/2-0.5)) if i is odd

Answer 1

At a first glance, the time and space analysis looks (roughly) correct. I haven't made a super close inspection, however, since it doesn't appear to be the focus of the question.

Regarding the time complexity for even / odd inputs, the answer is that the time complexity is O(sqrt(2)^i), regardless of whether i is even or odd.

In the even case, we have O(2^(i / 2 - 1)) ==> O(1/2 * sqrt(2)^i) ==> O(sqrt(2)^i).

In the odd case, we have O(2^(i / 2 - 0.5)) ==> O(sqrt(2) / 2 * sqrt(2)^i) ==> O(sqrt(2)^i).

What you've written is technically correct, but significantly more verbose than necessary. (At the very least, it's poor style, and if this question was on a homework assignment or an exam, I personally think one could justify a penalty on this basis.)