search
Log In
0 votes
98 views
Show that quicksort’s best-case running time is $\Omega(n\ lg\ n)$.
in Algorithms 98 views

2 Answers

0 votes
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.
0 votes

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/

Related questions

0 votes
1 answer
1
0 votes
1 answer
2
43 views
Show that the expression $q^2 +(n-q-1)^2$ achieves a maximum over $q=0,1,\dots ,n-1$ when $q=0$ or $q=n-1$.
asked Jun 28, 2019 in Algorithms akash.dinkar12 43 views
0 votes
2 answers
3
92 views
Show that the running time of QUICKSORT is $\Theta(n^2)$ when the array $A$ contains distinct elements and is sorted in decreasing order.
asked Jun 27, 2019 in Algorithms akash.dinkar12 92 views
1 vote
2 answers
4
...