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

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.

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