You can compute recursively as below: We use f(n) to represent the number of comparisons which the Quick-Sort algo needs to take running on an array of n elements.
Answer to question 1: f(n) = 2 * f(n/2) + n We can observe the following sequence of equations: f(n) = 4 * f(n/4) + 2 * n/2 + n = 4f(n/4)+2n f(n) = 8 * f(n/8) + 4 * n/4 + 2 * n/2 + n = 8f(n/8)+3n f(n) = 16 * f(n/16) + 4n ... So, we induce the final conclusion: f(n) = 2^k * f(n/2^k) + kn, where n/2^k > 1 Thus f(n) = O(n*logn) This is really a tight boundary! Answer to question 2: f(n) = f(n/3) + f(2n/3) +n Same as above, we can conclude that: f(n) = O(n*logn) On Wed, Aug 25, 2010 at 11:16 AM, sourav <[email protected]> wrote: > The median of a set of n values is the \lceil n/2 \rceilth smallest > value. > > 1. Suppose quicksort always pivoted on the median of the current > sub-array. How many comparisons would Quicksort make then in the worst > case? > 2. Suppose quicksort were always to pivot on the "n/3 th" smallest > value of the current sub-array. How many comparisons would be made > then in the worst case? > > Support your answer giving mathematical proof / approach to your > answer. > > > [Note: In case quick sort always partitions the sub-array into 0 and > n-1 elements (pivot comes to be first element or last element), then > total of n^2 comparisions are done] > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
