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.