# Solving the recursive equation $T(n)=T(k)+T(n-k-1)+O(n)$

The question is clear in the title. I am trying to solve this recursion as a part of showing that the worst case of quicksort algorithm occurs when $$k=0$$, but can't do it. I could do the following specific cases (by repeatedly using the same recursion):

1)$$T(n)=T(n-1)+O(n)$$
2)$$T(n)=2T(\frac n2)+O(n)$$

Can anybody please help me to solve this general case (or at least suggest some other way to prove that the worst case is $$k=0$$)?

P.S. I don't know Master's theorem, so I would appreciate a solution without using that (In case that is applicable here).

• Can you solve the case $k=1$? The case $k=2$? The general case (assuming that $k$ is constant!) is similar. Dec 31, 2020 at 13:33
• The more interesting case is when $k = \alpha n$, in which case you might need different methods. Some answers on this site already cover this case. Dec 31, 2020 at 13:34
• If you don't know the master theorem, there is a nice Wikipedia page in which you can find a full explanation, as well as countless other sources. If it is relevant to you, then instead of declaring your wish to stay away from it, you should go ahead and study it. Dec 31, 2020 at 13:35
• @YuvalFilmus, How can we assume that $k$ is constant? It is extremely likely to change in further steps of the sorting process. Dec 31, 2020 at 13:41
• While the master theorem isn't the correct tool here, I think that the attitude of ignoring the master theorem just because it's not in the material is counterproductive. Dec 31, 2020 at 14:13

Consider the recurrence $$T(n+1) = \max_{0 \leq k \leq n} T(k) + T(n-k) + n+1, \qquad T(0) = 0,$$ which is one formalization of the worst-case running time of quicksort. Let us show by induction that the maximum is attained at $$k = 0$$ (or $$k = n$$). We will show this while at the same time showing that $$T(n) = \frac{n(n+1)}{2}$$.
The base case, $$n=0$$, is clear. Now suppose that $$T(m) = \frac{m(m+1)}{2}$$ for all $$m \leq n$$, and consider $$T(n+1)$$. The function $$T(k)$$ is convex on the interval $$[0,n]$$ (we extend it to real values using the same formula), and so the maximum of $$T(k) + T(n-k)$$ is attained at $$k=0$$ (or $$k=n$$). Therefore $$T(n+1) = T(0) + T(n) + n+1 = \frac{n(n+1)}{2} + n+1 = \frac{(n+1)(n+2)}{2}.$$
Instead of arguing using convexity, we can also argue directly: $$T(k) + T(n-k) = \frac{k(k+1) + (n-k)(n-k+1)}{2} = \frac{n(n+1)}{2}-k(n-k),$$ which is clearly maximized (uniquely) when $$k = 0$$ or $$k = n$$.
• I could understand your direct argument, but the previous argument isn't clear to me (the part where you somehow extended it to real values and claimed that it is convex, and that $T(x)+T(n-x)$ for fixed $n$ is maximized at end point for a convex function). Can you please elaborate it a little? Dec 31, 2020 at 14:28
• If $T$ is (strictly) convex on $[0,n]$, then $T(x) + T(n-x)$ is maximized (uniquely) at the endpoints. Here we think of $T$ as defined on the real interval $[0,n]$. Dec 31, 2020 at 14:31