# 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
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 20, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}