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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
