How does one know T(a) is the base case in T(n) = T(n-a) + T(a) + cn

Question

T(n) = T(n-a) + T(a) + cn

Solve by drawing recursion tree.

Typically when solving other recursion tree problems, I've calculated the height of the tree in terms of when the subproblems reach T(1). Why is it in this case that the height of the tree is determined by the "base case" T(a) instead of T(1)?

Answer 1

One hint: T(a)=O(1)

Since a is already fixed, then T(a) is a constant, so are T(a-1),T(a-2),T(2) etc.

You don't need to calculate T(a) to the base case, as long as it's a constant.