1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

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.