Data Structures and Algorithms MCQ - Performance Analysis of Algorithms and Recurrences

106 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 remains is selected as pivot?

T(n) = T(n/2) + T(n/2) + O(n) (for partition) + O(n) (for finding median)
On solving above using
Masters Method T(n) = O(n log n)

107 Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into 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

In quicksort a set of number is reduced to sorting two smaller set. We take first element as key value and combine all other with this. A pivot element which splits list into two sublists each of which at least one fifth of element only (B), i.e. T(n) ≤ T(n/5) + T(4n/5) + n the problem.
Alternately
If one sublist contains 1/5 elements other contains 4/5 elements.
If T(n) number of comparisons for sorting n elements.
So, for 1/5 elements = T(1/5n)
and for 4/5 elements = T(4n/5)
So, T(n) ≤ T(n/5) + T(4n/5) + n.
Here, n = time to spilt

108 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?

Recurrance relation is
T (n) = T (n/4) + T (3n/4) + n
On solving using tree’s method.
T(n) = O(nlogn)

109 Let P be a quicksort program to sort numbers in ascending order using the first element as the pivot. Let t₁ and t₂ be the number of comparisons made by Pfor the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?

When first element or last element is chosen as pivot, Quick Sort‘s worst case occurs for the sorted arrays.
In every step of quick sort, numbers are divided as per the following recurrence.
T(n) = T(n-1) + O(n)

110 You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is

The Worst case time complexity of quick sort is O (n²). This will happen when the elements of the input array are already in order (ascending or descending), irrespective of position of pivot element in array.