Algorithm to find kth largest element from an unsorted array in linear time.

Algorithm

  1. If the number of elements in an array is large .Divide the array into arrays each with 5 elements ⇨ n/5 arrays.
  2. Compute Median of all arrays of 5 elements. This can be done by sorting each group and taking middle element. This results in time complexity of n/5 * 5log5. (Sorting each group takes 5log5, and we have n/5 arrays)
  3. All the computed medians from each sub-array are then collected into a new, smaller array.
  4. Now, compute median of this array
  5. Use this Median as Pivot in QuickSelect

Median > half of these n/5 group medians. So median > n/10 medians.

Also each median in respective group is greater then half element so in total median is greater then 3n/10 element. (why multiply with 3 ⇨ because median in subgroup will be greater than equal to 3 elements, including ltself.)

So in total median is greater then 3n/10 and lesser then 3n/10 element

Complexity

The overall time complexity of the algorithm can be analyzed as follows:

  • Median calculation within sub-arrays contributes O(n) time.
  • Recursive processing of the median array takes T(n/5) time, which can be further broken down using the Master Theorem for divide-and-conquer recurrences. For constant sub-array size (k), the solution converges to O(n).

Therefore, the total time complexity becomes O(n) + T(n/5) + O(n), which simplifies to O(n) due to the dominant linear term.