I am currently struggling with a problem on time complexity of the Quicksort algorithm in the average case.
I calculated the average time complexity of the algorithm to be
$T_n \quad = \quad \frac{1}{n} \cdot \sum_{k=1}^n \left( T_{k-1} + T_{n-k} + n - 1 \right)$
Which can also be written as
$T_n \quad = \quad n - 1 + \frac{2}{n} \cdot \sum_{k=1}^n T_{k-1}$
So far so well; now I have to calculate the term:
$n\cdot T_n - (n-1)\cdot T_{n-1}$
and solve the outcoming linear recursion of first order.
My ansatz is to insert the upper equation into this term, which gives me
$n\cdot T_n - (n-1)\cdot T_{n-1} \quad = \quad n^2 - n + 2 \cdot \sum_{k=1}^n T_{k-1} - \left[ (n-1)(n-2) + 2 \cdot \sum_{k=1}^{n-1} T_{k-1} \right]$
Whereof I get
$n\cdot T_n - (n-1)\cdot T_{n-1} \quad = \quad 2 \cdot \left[ (n-1) + T_{n-1} \right]$
Now, I am stuck. Because if I solve the equation for $T_n$, I obtain
$T_n \quad = \quad \frac{1}{n} \cdot \left[ (n+1) T_{n-1} + 2(n-1) \right]$
This is not linear though, meaning I made a mistake somewhere, or there is another way to solve this.
Does anyone have an idea how to carry on or how to solve this?
Sincerely, Octavius
I finally managed to get it down. I start from the above mentioned term
$n \cdot T_n \quad = \quad (n+1) \cdot T_{n-1} + 2(n-1)$
Since I only want to know magnitudes and asymptotic behavior I simply discard the $-2$ term, remaining with
$n \cdot T_n \quad = \quad (n+1) \cdot T_{n-1} + 2n$
which is equivalent to
$\frac{T_n}{n+1} \quad = \quad \frac{2}{n+1} + \frac{T_{n-1}}{n}$ .
Basically I am done now, because all I have to do is recursively insert the equation:
$\frac{T_n}{n+1} \quad = \quad \frac{2}{n+1} + \frac{2}{n} + \frac{T_{n-2}}{n-1} \quad = \quad \frac{2}{n+1} + \frac{2}{n} + \frac{2}{n-1} + \frac{T_{n-3}}{n-2} \quad = \quad \text{etc.}$
In a more compact form:
$\frac{T_n}{n+1} \quad = \quad 2 \cdot \sum_{j=2}^{n+1} \frac{1}{j}$
Which is the $(n+1)$-th partial sum of the harmonic series, meaning
$\sum_{j=2}^{n+1} \frac{1}{j} \quad \in \quad O(\log n)$
In conclusion:
$ T_n \quad \in \quad O(n \cdot \log n)$
That is what I wanted to find as a solution in agreement with relevant literature solutions.