1- What is the worst-case running time of Quicksort if the pivot is randomly cho

Question

1- What is the worst-case running time of Quicksort if the pivot is randomly chosen as the first element in the array. Explain.

2- Show that the average size of aleft is (n-1)/2 when the input to Quicksort is n distinct elements and the median M is randomly chosen from one of the elements.

3- Calculate the running time of a divide-and-conquer algorithm that requires three recursive calls (each with input-size n/2) and 3n 2 steps that include dividing the input, and using the three solutions to obtain the final solution.

Explanation / Answer

1. Worst case running time of Quicksort is O(n2 ) if pivot is randomly chosen as the first element in the array.

This worst case occurs when array is already sorted.

Worst case time analysis :

T(N) = T(N-1) +cN        where N is number of elements in array

as in partitioning lefthand side of pivot contains all elements smaller than pivot and right hand side of pivot contains elements greater than pivot.,

So, if array is already sorted and we pickup first element as pivot ,right hand side will contain N-1 elements.

T(N) = T(N-1) +cN on solving gives O(n2) time complexity.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.