The most effective algorithm to find the median of an unsorted array of size n…

Concept

Finding the median is a special case of the selection problem: locating the k-th smallest element (the order statistic) of an unsorted collection. A key result in algorithm design is that selection — and therefore the median — can be solved in worst-case linear time, i.e. time proportional to the number of elements, O(n), without first sorting the whole array.

Application

1. The median of an n-element array is the order statistic at rank n/2, so finding the median is exactly solving the selection problem for k = n/2.

2. The median-of-medians (BFPRT) algorithm chooses a provably good pivot: split the array into groups of 5, take the median of each group, then recursively take the median of those medians. This pivot guarantees a constant fraction of elements is discarded each step.

3. That guarantee yields the recurrence T(n) = T(n/5) + T(7n/10) + O(n), whose solution is O(n) — linear worst-case time. (Randomised Quickselect achieves the same O(n) on expectation with a simpler implementation.)

Cross-check / Contrast

• O(n log n) is the cost of the obvious approach — sort the array, then read the middle element. Sorting does strictly more work than needed (it orders every element), so it is not the most effective method.

• O(log n) is impossible: any correct algorithm must inspect every element at least once (an unseen element could be the median), so it cannot run faster than linear time.

• Since a linear-time method exists among the choices, O(n) is the most effective achievable time.