I have a recurrence relation: $$T(n) = T(n-a) + T(a) + n$$
which happens to be $O(n^2)$ complexity.
How do I now prove that:
$$a = n/2$$
is a tight upper bound for this relation? I have been pointed towards the Master Theorem and doing the analysis 'by hand' by substitution $2^k$ into the equation.
Not really sure how to solve this.
Any help would be greatly appreciated, thanks!
We claim that if: $$ T(n) = 2T(n/2) + n $$ then $T(n) = \Theta(n \log n)$. To see this, it suffices to prove by induction on $n$ that there exist constants $c,d,n_0 \geq 1$ such that for all $n \geq n_0$, we have that:
Base Case: I'll let you do this part.
Induction Hypothesis: Assume that $(\star)$ holds for all $n' < n$.
It remains to prove that $(\star)$ holds for $n' = n$. Indeed, observe that: \begin{align*} 2T(n/2) + n &= T(n) = 2T(n/2) + n \\ 2(c \tfrac{n}{2}\log \tfrac{n}{2}) + n &\leq T(n) \leq 2(d\tfrac{n}{2} \log \tfrac{n}{2}) + n &\text{by the ind. hyp.} \\ cn(\log n - \log 2) + n &\leq T(n) \leq dn (\log n - \log 2) + n \\ (cn\log n) + (\underbrace{1 - c \log 2}_{\geq~0})n &\leq T(n) \leq (dn \log n) - (\underbrace{d\log 2 - 1}_{\geq~0})n \\ cn \log n &\leq T(n) \leq dn\log n \end{align*} where the last step used the fact that we can choose $c \leq \frac{1}{\log 2}$ and $d \geq \frac{1}{\log 2}$.