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}\]