Cormen Edition 3 Exercise 7.4 Question 2 (Page No. 184)

Question

Show that quicksort’s best-case running time is $\Omega(n\ lg\ n)$.

Answer 1

the best case in quicksort is when elements is in unsorted order then the function has to run only f(n)=2T(n/2)+n

when the elements are is increasing or decreasing oder than f(n) value become f(n)=T(n-1)+n because then the pivot element either present in first position or last position so the number of comparisons becomes (n-1) for sorting.

Answer 2

We'll use the substitution method to show that the best-case running time is $\Omega(n\lg n)Ω(nlgn).$ Let $T(n)$ be the best-case time for the procedure QUICKSORT on an input of size n. We have

T(n) = $\min _{1 \le q \le n - 1} (T(q) + T(n - q - 1)) + \Theta(n).T(n)=1≤q≤n−1min​(T(q)+T(n−q−1))+Θ(n).$

Suppose that $T(n) \ge c(n\lg n + 2n)T(n)≥c(nlgn+2n)$ for some constant c. Substituting this guess into the recurrence gives

\begin{aligned} T(n) & \ge \min _{1 \le q \le n - 1}(cq\lg q + 2cq + c(n - q - 1) \lg(n - q - 1) + 2c(n - q - 1)) + \Theta(n) \\ & = (cn / 2)\lg(n / 2) + cn + c(n / 2 - 1)\lg(n / 2 - 1) + cn - 2c + \Theta(n) \\ & \ge (cn / 2)\lg n - cn / 2 + c(n / 2 - 1)(\lg n - 2) + 2cn - 2c\Theta(n) \\ & = (cn / 2)\lg n - cn / 2 + (cn / 2) \lg n - cn - \lg n + 2 + 2cn - 2c\Theta(n) \\ & = cn\lg n + cn / 2 - \lg n + 2 - 2c + \Theta(n). \end{aligned}$T(n)​≥1≤q≤n−1min​(cqlgq+2cq+c(n−q−1)lg(n−q−1)+2c(n−q−1))+Θ(n)=(cn/2)lg(n/2)+cn+c(n/2−1)lg(n/2−1)+cn−2c+Θ(n)≥(cn/2)lgn−cn/2+c(n/2−1)(lgn−2)+2cn−2cΘ(n)=(cn/2)lgn−cn/2+(cn/2)lgn−cn−lgn+2+2cn−2cΘ(n)=cnlgn+cn/2−lgn+2−2c+Θ(n).​$

Taking a derivative with respect to q shows that the minimum is obtained when $q = n / 2q=n/2.$ Taking c large enough to dominate the $−\lg n + 2 − 2c + \Theta(n)−lgn+2−2c+Θ(n)$ term makes this greater than $cnlgn$, proving the bound.

Ref: https://walkccc.github.io/CLRS/Chap07/7.4/