prove $T(n)=max_{1\leq q\leq n-1}(T(q)+T(n-q))+\theta(n) \\~\\ \Longrightarrow T(n)=O(n^{2})$

Question

let $T(i)$ denote the worst-case running time of QuickSort algorithm on an input of size $i$.

Then, the recurrence for the worst-case running time is given by:

$$T(n)=max_{1\leq q\leq n-1}(T(q)+T(n-q))+\theta(n)$$

I need to prove that: $T(n)=O(n^{2})$

I'm trying to solve with complete induction.

assumption: $\forall1\leq q\leq n-1:T(q)\leq cq^{2}$

step: $$T(n) \leq max_{1\leq q\leq n-1}\left(T(q)+T(n-q))\right)+\theta(n) \\ \leq max_{1\leq q\leq n-1}\left(cq^{2}+c(n-q)^{2}\right)+\theta(n)\\ \leq c\cdot1^{2}+c(n-1)^{2}+\theta(n)=cn^{2}-2c(n-1)+\theta(n)$$

but I don't know how to show from here that $T(n)\leq cn^{2}$

Thanks and sorry if I have English mistakes :(

Answer 1

If, for example, your $\theta(n)$ is no greater than $dn$, then given a $T(n)$, by repeatedly splitting things up, you can get something like this in at most $n-1$ steps : $$ \begin{align*} T(n)&=T(q)+T(n-q)+\theta(n)\\ &=T(q')+T(q-q')+T(n-q)+\theta(q)+\theta(n)\\ &=\cdots\\ &=T(1)+T(1)+\cdots+T(1)+\theta(a_{1})+\theta(a_{2})+\cdots+\theta(a_{n-1})\\ &\leq nT(1)+\sum_{i=1}^{n-1}da_{i}\\ &\leq nT(1)+(n-1)\cdot dn\\ &=O(n^{2}). \end{align*}$$ where the $a_{i}$'s are less than or equal to $n.$