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.

The recurrence \(T(n) = T(n-a) + T(a) + cn\) has the following recursion tree:

Adding up the costs of each level of the tree:

\[\begin{split} T(n) & = cn + (cn) + (cn - ca) + (cn - 2ca) + \cdots + \Theta(1) \\ & = cn + \sum\limits_{i=1}^{n/a}(c(n-ia) + ca) \\ & = cn + \sum\limits_{i=1}^{n/a}cn - \sum\limits_{i=1}^{n/a}cia + \sum\limits_{i=1}^{n/a}ca \\ & = cn + c \frac{n^2}{a} - \frac{cn(a+n)}{2a} + cn \\ & = c \frac{n^2}{a} - c \frac{n^2}{2a} - c \frac{n}{2} + 2cn \\ & = c \frac{n^2}{2a} + \frac{3}{2}cn \\ & = \Theta(n^2) \\ \end{split}\]

In order to produce a tight asymptotic bound, we first guess that \(T(n) \leq cn^2\) in order to show that \(T(n) = O(n^2)\). Substituting this into the recurrence yields

\[\begin{split} T(n) & \leq c(n - a)^2 + ca + cn \\ & = cn^2 -2can + ca^2 + ca + cn \\ & = cn^2 -c(2an - a^2 - a - n) \\ \leq cn^2 \\ \end{split}\]

Where the last step holds for all \(n > a\). Next we guess that \(T(n) \geq \frac{c}{2a}n^2\) in order to show that \(T(n) = \Omega(n^2)\). Substituting this into the recurrence yields

\[\begin{split} T(n) & \geq \frac{c}{2a}(n-a)^2 + ca + cn \\ & = \frac{c}{2a}(n^2 - 2an + a^2) + ca + cn \\ & = \frac{c}{2a}n^2 = cn + \frac{1}{2}ca + ca + cn \\ & = \frac{c}{2a}n^2 + \frac{3}{2}ca \\ & \geq \frac{c}{2a}n^2 \\ \end{split}\]

Where the last step holds for all \(a\). Therefore \(T(n) = \Theta(n^2)\).

The follow LaTex code was used to generate the above recursion tree:

\documentclass[12pt]{article}
\usepackage{forest}
\usepackage{tikz-qtree}
\begin{document}

\begin{figure}
\begin{minipage}[b]{0.5\linewidth}
\centering
\begin{tikzpicture}[scale=.75,sibling distance=0pt]
\Tree [.$cn$ 
        [.$c(n-a)$ 
          [.$c(n-2a)$ 
            [.$c(n-3a)$ 
              [.$\vdots$ 
                [.$\Theta(1)$ ] ] ]
            [.$ca$ ] ] 
          [.$ca$ ] ] 
        [.$ca$ ] ]
\end{tikzpicture}
\end{minipage}
\begin{minipage}[b]{.1\linewidth}
\centering
\begin{tikzpicture}[scale=.75,sibling distance=0pt]
\Tree [.$cn$
        [.$cn$
          [.$cn-ca$
            [.$cn-2ca$
              [.$\vdots$ 
                [.$\Theta(1)$ ] ] ] ] ] ]
\end{tikzpicture}
\end{minipage}
\end{figure}
\end{document}