For recurrence T(n) = T(n − a) + T(a) + n, prove that T(n) = O(n^2 ) complexity I have been looking over this question for hours now, and can't seem to work it out. It's a question regarding the complexity of sorting algorithms
Assume that $a$ is constant and so is $T(n)$ for $n ≤ a$. For recurrence $T(n) = T(n −
a) + T(a) + n$, prove that $T(n) = O(n^2)$
I don't really know where to begin with the question, any help is greatly appreciated!

To show that $T(n) = O(n^2)$, we will prove by induction on $n$ that there exist constants $c, n_0$ such that for all $n \geq n_0$, we have that:
$$
T(n) \leq cn^2
$$
Base Case: I'll let you do this part.
Induction Hypothesis: Assume that the claim holds for all $n' < n$.
It remains to prove that the claim holds for $n' = n$. Choose any constant $a \geq 1$, and assume that $T(n) = k \geq 1$ for all $n \leq a$. Now define:
$$
c = \frac{1}{a} > 0 \qquad\text{and}\qquad n_0 = \frac{a^2c + k}{2ac - 1} > 0
$$
Observe that if $n \geq n_0$, then since $1 - 2ac = 1 - 2a(\frac{1}{a}) = 1 - 2 = -1 < 0$, we have that:
$$
(1 - 2ac)n \leq (1 - 2ac)n_0 = (1 - 2ac)\frac{a^2c + k}{2ac - 1} = -(a^2c + k) \tag{$\star$}
$$
Hence, these chosen constants will do the trick, since for all $n \geq n_0$, we have that:
\begin{align*}
T(n)
&= T(n - a) + T(a) + n \\
&= T(n - a) + k + n \\
&\leq c(n - a)^2 + k + n &\text{by the induction hypothesis}\\
&= c(n^2 - 2an + a^2) + k + n \\
&= cn^2 + (1 - 2ac)n + (a^2c + k) \\
&\leq cn^2 - (a^2c + k) + (a^2c + k) &\text{by $(\star)$}\\
&= cn^2
\end{align*}
which completes the induction. $~~\blacksquare$
