# Quicksort $T(n)_{best}=\Omega(n\log n)$ proof

About the proof that quicksort has $T(n)_{best}=\Omega(n\log n)$.

I can't find this specific aspect anywhere online which is strange. I'm going through a proof for this in a book and I don't understand something, it says that about analyzing the "cost" of a level in the recursion tree that:

Since the recurrence relation for quicksort is: $T_{best}= T(i-1)+T(n-i) + n$, then the cost of the root is $n$, and the cost of the level below it is $n-1$, in general: if a level has $x$ vertices, then the cost of the next level is smaller by $x$.

How is that possible? It's easy to see that each complete level has a total cost of $n$.

Also about the first level, if we plug $i=1$ to the equation, we indeed see that one recursive call (say left) leaves a "cost" of $n-1$ but the second call (say right) has a cost of $1$ so the total for the first level is $n$ and not $n-1$..

The proof then goes on to say that level $i-1$ has at most $2^{i-1}$ vertices, therefore the cost of level $i$ is at least $n-(1+2+...2^{i-1}) > n- 2^{i}$, therefore the cost of each of the $\log n$ levels is $\Omega (n)$.

You mentioned the quicksort recursion: $$T_{best}(n) = \min_i [T_{best}(i-1) + T_{best}(n-i) + n].$$ Note how in this recursion $(i-1) + (n-i) = n-1$. This is because the two subproblems don't involve the pivot. This is the case for any node in the recursion tree: if a node corresponds to an array of length $m$, then its two children correspond to arrays of lengths $m_1,m_2$ where $m_1 + m_2 = m-1$. In particular, if a certain level has $x$ nodes then the sum of lengths at that level $S$ and the sum of lengths at the next level $T$ satisfies $S = T + x$; the $x$ pivots disappear from the recursion.
Denote by $N_i$ the number of nodes at depth $i$, and by $S_i$ the sum of lengths at depth $i$. Assuming we start counting at level 0, we have $S_0 = n$, $S_{i+1} = S_i - N_i$, and $N_i \leq 2^i$. You can prove by induction that $$S_i \geq n - (2^i-1).$$ In particular, $S_{\log_2 n} \geq 1$ (assuming $n$ is a power of 2), so there are at least $\log_2 n$ levels of recursion. Furthermore, $$\sum_{i=0}^{\log_2 n} S_i \geq \sum_{i=0}^{\log_2 n} (n+1-2^i) = (n+1)\log_2 n - (2n-1) = \Omega(n\log n).$$ Since $\sum_{i=0}^\infty S_i$ is exactly the running time of quicksort (up to constants), we see that quicksort always takes at least $\Omega(n\log n)$.
• The argument of cs.stackexchange.com/a/52365/683 can also be adapted to give an $\Omega(n\log n)$ lower bound. – Yuval Filmus Feb 15 '16 at 20:42
• Toda. What purpose does the $\min_i$ serve in the equation? – shinzou Feb 15 '16 at 20:56
• It extracts the best choice of $i$. – Yuval Filmus Feb 15 '16 at 21:10