Let S be a set of n distinct positive integers, where n is odd. The median of S is the (n+1)/2th smallest number of this set - i.e., the number in the middle of the set once the set is sorted. For example, if S = [70, 10, 20, 60, 30], then the sorted set is [10, 20, 30, 60, 70], from which we see that the median is 30. There is an obvious linearithmic algorithm to determine the median of S. First you sort the set, which takes O(n log n) time. Then you output the value of S[(n+1)/2}, which takes O(1) time. But is this the best we can do? Here is a bold claim: there is an O(n) algorithm to determine the median of set S. Determine whether the above claim is TRUE or FALSE.
Let S be a set of n distinct positive integers, where n is odd.
The median of S is the (n+1)/2th smallest number of this set - i.e., the number in the middle of the set once the set is sorted.
For example, if S = [70, 10, 20, 60, 30], then the sorted set is [10, 20, 30, 60, 70], from which we see that the median is 30.
There is an obvious linearithmic
Here is a bold claim: there is an O(n) algorithm to determine the median of set S.
Determine whether the above claim is TRUE or FALSE.
The claim is TRUE.
Quick Sort is the algorithm to determine the median of set S. It is used as a sorting algorithm to sort the set S in first step. In the Quick Sort algorithm, a pivot element is being picked first and then move the pivot element to its correct position, as per the sorting condition, and then the partition of the set is done around it.
The idea in this procedure is that the quick sort will be stopped at the point where the pivot element itself is that particular nth smallest element and hence the quicksort will not be completed. There will be recurrence of only one side of the pivot element and not both sides, as per the position of pivot element, hence the time will be consumed comparatively less.
The time complexity, in the worst case scenario of this algorithm is O(n2), though the average case scenario is O(n) on an average. As in the worst case, a randomized function tries to pick a corner element always.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
