How to prove that if $T(n)=\max_{1\le q \le n-1}(T(q)+T(n-q))+\Theta(n)$ then $T(n)=O(n^2)$

Question

I have this recursion relation: $T(n)=\max_{1\le q \le n-1}(T(q)+T(n-q))+\Theta(n)$.

How do I show that: $T(n)=O(n^2)$

Thank you!!

(P.S. I hope it's OK to ask it, but I'm looking for the simple solution...)

Answer 1

Hint: Induction on $n.$

The base case $n=1$ is trivial. Let the statement holds for $<n$ (hypothesis). For $n,$ use the fact that if $f_1 \in O(g_1), f_2 \in O(g_2)$ then $f_1+f_2 \in O(|g_1|+|g_2|).$