Sorting
Q21.
In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?Q23.
You have an array of n elements. Suppose you implement quick sort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance isQ24.
Which of the following sorting algorithms has the minimum running time complexity in the best and average case?Q26.
The median of n elements can be found in O(n) time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?Q27.
Give the correct matching for the following pairs: \begin{array}{ll|ll}\hline \text{(A)} & \text{$O (\log n)$} & \text{(P)} & \text{Selection sort} \\\hline \text{(B)} & \text{$O (n)$} & \text{(Q)}& \text{Insertion sort} \\\hline \text{(C)}& \text{$O (n \log n)$} & \text{(R)} & \text{Binary search} \\\hline \text{(D)} & \text{$O (n^2)$} &\text{(S)} & \text{Merge sort} \\\hline \end{array}Q28.
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. ThenQ29.
Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n ( \geq2) numbers? In the recurrence equations given in the options below, c is a constant.Q30.
The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of