For recurrence T(n) = T(n − a) + T(a) + n, prove that T(n) = O(n^2 ) complexity

Question

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!

Answer 1

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$

Answer 2

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)