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!

I might start by setting $a=1$ and seeing if I can solve the simpler problem. Then $a=2$. And hopefully by that time I'll have some ideas for solving the general problem.
However, given that you're already told that $T(n) = O(n^2)$, you might be better off seeking to verify that that is the solution, rather than trying to derive it.
(in fact, frequently for this sort of problem, the approach is that you do some exploratory work until you can guess at what the solution is, and then you try to verify the guess)
