Data Structures and Algorithms - Performance Analysis of Algorithms and Recurrences
- Option : B
- Explanation : 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)
- Option : B
- Explanation : 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
- Option : B
- Explanation : Recurrance relation is T (n) = T (n/4) + T (3n/4) + n On solving using tree’s method. T(n) = O(nlogn)
- Option : C
- Explanation : 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)
- Option : A
- Explanation : The Worst case time complexity of quick sort is O (n2). 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.
