Finding the base case for T(n) = T(n - a) + T(a) + cn

Question

I was solving the recurrence using Recursion tree method: $$ T(n) = T(n - a) + T(a) + cn$$

When I started solving I could easily conclude the fact that $T(a)$ would have total cost computation in the form of:

$$h*ca$$ But I could not figure out on how to solve the base case.

I know that $T(n-a)$ would be at base case when $n=a$.

But how to compute the height $h$ of the recurrence. I know the base case can be defined as: $$n-ia=0$$

I have seen the previous examples in the book Introduction to Algorithms which quotes:

The subproblem size for a node at depth $i$ is $n/4^i$ . Thus, the subproblem size hits $n=1$ when $n/4^i=1$ or, equivalently, when $i = \log_4 n$

For the recurrence: $T(n)= 3T(n/4)+ cn^2$

So, coming to the point what would be the base case such that the sub-problem size hits $n= ?$ like in the above example.

Would it be $n=a$?

Please correct me if I am wrong. Thank you.

Answer 1

Every $0\le k\le a$ yields the base case $T(k)$. If you are trying to solve the big-O of the recurrence, then you may as well assume that there is some $c$ where $T(k)\le c$ for every base case $k$. It will help making the computation a bit easier