Median Quicksort

Computer Science Level 3

Suppose we have an $O(n)$ algorithm that finds the median of an unsorted array of numbers. If we use the median as a pivot in a Quicksort implementation, what will be the worst case time complexity of the modified algorithm?

O(\log(n))

O(\log\log(n))

O(n)

O(n\log n)

1 solution

Tom Engelsman
Oct 17, 2020

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 two 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 $\boxed{O(n \cdot log(n))}.$

Median Quicksort

1 solution

0 pending reports