Example on Quick Sort

In quick-sort for sorting \(n\) elements, the \((\frac{n}{4})^{th}\)smallest element is selected as pivot using an O(n) time algorithm. What
is the worst case time complexity of the quick sort ?

A) \(\Theta(n)\)

B) \(\Theta(n \log n)\)

C) \(\Theta(n^2)\)

D) \(\Theta(n^2 \log n)\)

Things you need to know

Refer: http://www.techtud.com/video-lecture/analysis-quick-sort-and-problems-it-0


Choosing the \((\frac{n}{4})^{th}\) smallest element as the pivot element  divides the problem of sizez \((\frac{n}{4} ) \ \ and \ \ (\frac{3n}{4})\)

\(\therefore \text{Total time } = \text{Time for partitioning } + \text{Time to solve sub-problems}\)

\(\hspace{30mm} = \color{red}{\Theta(n)} + \color{green}{T(\frac{n}{4})} + \color{green}{T(\frac{3n}{4})}\)

\(\hspace{30mm} \leq \color{red}{\Theta(n)} + \color{green}{T(\frac{n}{4})} + \color{green}{T(\frac{n}{4})}\)

\(\hspace{30mm} \leq \color{green}{2T(\frac{n}{4})} +\color{red}{\Theta(n)} \)

Applyting masters theorem,

\(\text{Time} \approx \color{blue}{ \Theta(n \log n)}\)

Hence, Ans (B)