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

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 :(

• but for positive c it is true no? it's parabola which gets maximum value on edges. my assumption is for c>0 Oct 22, 2021 at 13:53
• yes, my mistake. Oct 22, 2021 at 14:00

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.$$