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

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?

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

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