Show that the best case time complexity of Quicksort is $\Omega(n \log n)$

Question

I am trying to show that the best case time complexity of Quicksort is $\Omega(n \log n)$.

The following recurrence describes the best-case time complexity of Quicksort:

$$T(n) = \min_{0 \le q \le n-1} \left(T(q) + T(n-q-1) \right) + \Theta(n).$$

But I have difficulty in proving that $T(n) = \Omega(n \log n)$ using the recurrence above.

So how to solve this recurrence?

Answer 1

Let us replace $\Theta(n)$ with $n$, for concreteness, and assume a base case of $T(0) = 0$. Let's try to prove inductively that $T(n) \geq cf(n)$, where $f(n) = n\log n$ for all $n$ (where $0\log 0 = 0$).

During the proof, we will need to minimize $f(q) + f(m-q)$ for $0 \leq q \leq m$. Since $f'(n) = \log n + 1$, any minimum point must satisfy $$ \log q + 1 = \log (m-q) + 1, $$ that is, $q = m/2$. Since $2f(m/2) = m\log(m/2)$ whereas $f(0) + f(m) = m\log m$, we see that $q = m/2$ is indeed a minimum.

We are now ready to prove inductively that $T(n) \geq cf(n)$. The base case is obvious. For the inductive step, note that for each $q \in \{0,\ldots,n-1\}$, $$ T(q) + T(n-1-q) \geq c(f(q) + f(n-1-q)) \geq c(n-1) \log((n-1)/2). $$ Therefore to complete the proof, we need to show that $$ c(n-1) \log \frac{n-1}{2} + n \geq cn\log n. $$ This holds trivially for $n=1$, and holds for all $n \geq 2$ when $c = 1/\log 3$.

Altogether, this shows that $T(n) \geq n\log_3 n$.

Answer 2

You can use the recursion tree method.

The amount of work on the level at depth $0$ is at least $c n$ for some constant $c$ (from the $\Theta(\cdot)$ notation). The amount of work at depth $1$ is at least $c q + c (n-q -1) = c(n-1)$. The amount of work on the next level is at least $c(n-3)$ and, in general, the total amount of work on the level at depth $d$ is at least $c(n - 2^d - 1)$. You can prove this by induction on $d$.

The number of levels with non-zero amount of work must be at least $1+\log(n-2)$, therefore the total time complexity must be at least $\sum_{d=0}^{\log(n) /2} c(n - 2^d - 1) \ge c \sum_{d=0}^{\log(n) /2} (n-\sqrt{n}-1) = c \sum_{d=0}^{\log(n) /2} \Omega(n) = \Omega(n \log n)$.