Algorithm
Q191.
Which of the following sorting algorithms has the minimum running time complexity in the best and average case?Q193.
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?Q194.
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}Q195.
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. ThenQ196.
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.Q197.
The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order ofQ198.
A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation isQ199.
What is the number of swaps required to sort n elements using selection sort, in the worst case?Q200.
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Following algorithm(s) can be used to sort n in the range [1\ldots n^3] in O(n) time