0
$\begingroup$

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

$\endgroup$
15
  • $\begingroup$ Can you solve the case $k=1$? The case $k=2$? The general case (assuming that $k$ is constant!) is similar. $\endgroup$ – Yuval Filmus Dec 31 '20 at 13:33
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 31 '20 at 13:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 31 '20 at 13:35
  • $\begingroup$ @YuvalFilmus, How can we assume that $k$ is constant? It is extremely likely to change in further steps of the sorting process. $\endgroup$ – Martund Dec 31 '20 at 13:41
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 31 '20 at 14:13
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ – Martund Dec 31 '20 at 14:28
  • $\begingroup$ 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]$. $\endgroup$ – Yuval Filmus Dec 31 '20 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.