2
$\begingroup$

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

Does anyone understand the part that I'm asking about?

Alternatively, is there a proper rigorous proof for this somewhere online?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The argument of cs.stackexchange.com/a/52365/683 can also be adapted to give an $\Omega(n\log n)$ lower bound. $\endgroup$ – Yuval Filmus Feb 15 '16 at 20:42
  • $\begingroup$ Toda. What purpose does the $\min_i$ serve in the equation? $\endgroup$ – shinzou Feb 15 '16 at 20:56
  • $\begingroup$ It extracts the best choice of $i$. $\endgroup$ – Yuval Filmus Feb 15 '16 at 21:10

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.