Question

suppose we have a0(n) time algorithm that finds median of an unsorted array. now consider a quicksiet implementation where we first median using the above algorithm, then use median as pivot. what will be the worst case time complexity of this modified quicksort​

Answer 1

Explanation:

Suppose we have a O(n) time algorithm that finds median of an unsorted array.

Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.

(A) O(n^2 Logn)

(B) O(n^2)

(C) O(n Logn Logn)

(D) O(nLogn)

Answer: (D)

Explanation: If we use median as a pivot element, then for each iteration it takes O(n) time to find median from given function and every time the array partitions in 2 subparts.

so the recurrence equation becomes.

T(n) = 2T(n/2) + O(n)

The above recurrence can be solved using Master Method. It falls in case 2 of master method

which results in complexity O(nlogn)