Use a recursion tree to give an asymptotically tight solution to the recurrence $$T(n) = T(n - a) + T(a) + cn$$, where $$a \geq 1$$ and $$c > 0$$ are constants.

Rate of increase in number of subproblems in each recursion = 1

Rate of decrease in subproblem size = 1 with $$a$$ less input at every depth

Hence at depth $$i = 0, 1, 2, \dots, n/a$$ of the tree, there are 2 nodes each of total cost of $$c(n - ia) + ca$$.

Hence, total cost of the tree is:

\begin {aligned} T(n) & = \sum_{i = 0}^{n/a} (c(n - ia) + ca) \\ & = cn \cdot \frac n a + ca \cdot \frac n a - ca \sum_{i = 0}^{n/a} i \\ & = \frac {cn^2} {a} + cn - ca \cdot \frac {n/a (n/a + 1)} 2 \\ & = \frac {cn^2} {a} + cn - ca \cdot \frac {n(n + a)} {2a^2} \\ & = \frac {cn^2} {a} + cn - \frac {cn(n + a)} {2a} \\ & = \frac {3cn^2} {2a} + \frac {cn} {2} \\ & = \Theta(n^2) \end {aligned}