1
$\begingroup$

From this website, it states that the average case of Quicksort algorithm is

  T(n) = T(n/9) + T(9n/10) + θ(n)

Im a bit confused. Is it supposed to be ?

  T(n) = T(n/10) + T(9n/10) + θ(n)
$\endgroup$
  • 1
    $\begingroup$ You are right, there's a typo in the website. However, this is not the complete analysis of average case complexity of quicksort, you'll have to find a different source for it. $\endgroup$ – Gokul Jul 18 at 13:37
  • 2
    $\begingroup$ The website is completely wrong. There are other sources out there with a proper treatment of the problem, possibly not using any recurrence. $\endgroup$ – Yuval Filmus Jul 18 at 14:39
3
$\begingroup$

The average case running time of quicksort satisfies the recurrence $$ T(n) = \frac{1}{n} \sum_{i=1}^n [T(i-1) + T(n-i)] + \Theta(n), $$ with base case $T(0) = \Theta(1)$.

In view of solving this recurrence, let us replace $\Theta(n)$ with $n+1$ and $\Theta(1)$ with $2$ (the reason for these specific choices will become apparent below). Changing the order of summation, we get $$ T(n) = \frac{2}{n} \sum_{i=0}^{n-1} T(i) + n + 1, $$ and so $$ nT(n) = 2\sum_{i=0}^{n-1} T(i) + n(n+1). $$ This implies that $$ (n+1)T(n+1) - nT(n) = 2T(n) + 2(n+1), $$ and so $$ T(n+1) = \frac{n+2}{n+1} T(n) + 2. $$ Unrolling this gives $$ \begin{align*} T(n) &= 2 + \frac{n+1}{n} T(n-1) = 2 + \frac{n+1}{n} 2 + \frac{n+1}{n-1} T(n-2) = \cdots \\ &= 2\left[1 + \frac{n+1}{n} + \frac{n+1}{n-1} + \cdots + \frac{n+1}{2}\right] + \frac{n+1}{1} T(0) \\ &= 2\left[1 + \frac{n+1}{n} + \frac{n+1}{n-1} + \cdots + \frac{n+1}{2} + \frac{n+1}{1} \right] \\ &= 2(n+1) \left[\frac{1}{n+1} + \cdots + \frac{1}{1} \right] \\ &= 2(n+1) H_{n+1} \\ &= \Theta(n\log n). \end{align*} $$


A different way of analyzing the running time of quicksort in the average case computes the average number of comparisons. Due to linearity of expectation, it suffices to calculate the probability that two elements are compared. You can see both methods worked out in Section 3.4 of lecture notes from CMU.

$\endgroup$

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.