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

  • $\begingroup$ Okay. Got it. Thank you. $\endgroup$ Jun 27 '20 at 5:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.