Consider the Quicksort algorithm. Suppose there is a procedure for finding a…
PYQ GATE 2008
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then
- A.
T(n) <= 2T(n/5) + n
- B.
T(n) <= T(n/5) + T(4n/5) + n
- C.
T(n) <= 2T(4n/5) + n
- D.
T(n) <= 2T(n/2) + n
Attempted by 628 students.
Sign up free to check your answer
Sign up freeLoading lesson…