Show that the average case complexity of quick sort technique is O (n log n).
Subject Algorithm Design
NU Year Set: 2.(a) Marks: 4 Year: 2008

When quicksort always has the most unbalanced partitions possible, then the original call takes c, n time for some constant c, the recursive call on n, minus, 1elements takes c, left parenthesis, n, minus, 1, right parenthesis time, the recursive call on n, minus, 2 elements takes c, left parenthesis, n, minus, 2, right parenthesis time, and so on. Here's a tree of the subproblem sizes with their partitioning times:

When we total up the partitioning times for each level, we get
\begin{aligned} cn + c(n-1) + c(n-2) + \cdots + 2c &= c(n + (n-1) + (n-2) + \cdots + 2) \\ &= c((n+1)(n/2) - 1) \ . \end{aligned}
 
The last line is because 1 + 2 + 3 + \cdots + n is the arithmetic series, as we saw when we analyzed selection sort. (We subtract 1 because for quicksort, the summation starts at 2, not 1.) We have some low-order terms and constant coefficients, but when we use big-Θ notation, we ignore them. In big-Θ notation, quicksort's worst-case running time is \Theta(n^2).
Login to post your comment.