The Gateway to Computer Science Excellence

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.

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,271 answers

198,141 comments

104,782 users