Difficulty: Intermediate | Prerequisites: Basic probability, expected value, indicator random variables, Quicksort analysis.
Randomised Quicksort runs in O(n log n) expected time, but that says nothing about how often it is slow. If we could guarantee a pivot near the median every time, the worst case would also be O(n log n). This topic develops a linear-time randomised algorithm that finds an element with rank in the middle fifth of the array, with high probability. The technique of sampling, checking, and repeating ("boosting") is a recurring pattern throughout randomised algorithm design.
A "near median" is any element whose rank falls in the middle fifth of a set (between 2n/5 + 1 and 3n/5). Picking a random element hits this range with probability at least 1/5. You can verify a candidate in O(n) time, so repeating the sample-and-check loop a constant number of times boosts the success probability to 99% or higher, all in O(n) time.
Rank
The position of an element when the set is sorted. rank(a) = k means a is the kth smallest element. In simple terms, rank tells you where an element sits in the sorted order.
Near median
An element whose rank is between 2n/5 + 1 and 3n/5 (inclusive). Think of it as anything in the "middle fifth" of the sorted set, not necessarily the exact median.
Probability boosting (repetition / amplification)
The technique of repeating a randomised algorithm multiple independent times to drive the failure probability down exponentially. In simple terms, if one trial succeeds with probability p, then k independent trials all failing has probability (1 - p)^k, which shrinks fast.
The set S has n elements (n divisible by 5).
The near-median range spans ranks 2n/5 + 1 through 3n/5, which is n/5 elements.
If we pick a uniformly random element a from S, the probability it lands in this range is (n/5) / n = 1/5.
So the simplest algorithm (just output a random element) succeeds with probability at least 1/5.
Given S and a candidate a, determine whether a is a near median:
In one pass through S, count how many elements are less than a (call this L) and how many are greater (call this G). This takes O(n) time.
rank(a) = L + 1.
a is a near median if and only if 2n/5 + 1 ≤ L + 1 ≤ 3n/5.
Repeat the following loop:
Pick a random a from S.
Check if a is a near median (O(n) time per check).
If yes, output a and stop.
If no, go back to step 1.
Repeat for at most k trials. Each trial fails independently with probability at most 4/5. After k trials, the probability that all fail is at most (4/5)^k.
We need (4/5)^k ≤ 0.01, so k ≥ log(0.01) / log(4/5) ≈ 20.6. Taking k = 21 trials suffices.
Total running time: O(kn) = O(21n) = O(n), since k is a constant.
The success probability is at least 1 - (4/5)^21 > 0.99.
\Pr[\text{random element is a near median}] = \frac{n/5}{n} = \frac{1}{5}\Pr[\text{all } k \text{ trials fail}] \leq \left(\frac{4}{5}\right)^kk \geq \frac{\ln(0.01)}{\ln(4/5)} \approx 20.6 \implies k = 21 \text{ suffices for 99\%}Finding a near-median pivot is how practical Quicksort implementations avoid worst-case O(n²) behaviour. The sample-and-verify pattern is used in load balancing (pick a random server, check if it is lightly loaded, retry if not) and in distributed consensus protocols.
Students often think "near median" means the exact median. It does not: any element in the middle fifth of the ranking qualifies.
Students sometimes forget that the 1/5 probability comes from the fraction of elements in the near-median range, not from some property of the random number generator.
A common error is computing the number of trials needed for 99% success by using 1/5 directly rather than (4/5)^k for the failure probability.
Students sometimes claim the verification step is O(n log n) because they think sorting is needed. It is not: a single linear scan suffices.
⚠️ Know the definition of near median precisely: rank between 2n/5 + 1 and 3n/5 inclusive.
⚠️ Be able to compute the number of repetitions k needed for a given confidence level.
⚠️ Understand why the overall running time is still O(n) even though we repeat O(1) times: each iteration is O(n), and a constant times O(n) is O(n).
⚠️ The "sample, verify, repeat" pattern appears frequently in exam questions about randomised algorithms.
True or False: The near median of a set of 100 elements is any element with rank between 41 and 60 inclusive. (True)
Fill in the blank: The probability a random element is a near median is at least ______. (1/5)
True or False: To verify whether a candidate is a near median, you must sort the array. (False: a linear scan counting elements above and below suffices.)
Fill in the blank: To achieve 99% success, you need at least ______ independent trials. (21)
Q: Why does a random element land in the near-median range with probability at least 1/5?
A: The near-median range covers ranks 2n/5 + 1 to 3n/5, which is exactly n/5 elements out of n total. Uniform random selection gives each element equal probability 1/n, so the probability of landing in the range is (n/5)/n = 1/5.
Q: Describe an O(n)-time algorithm to check whether a given element a is a near median of S.
A: Scan S once, counting elements strictly less than a (call this L) and strictly greater than a (call this G). Then rank(a) = L + 1. Check whether 2n/5 + 1 ≤ L + 1 ≤ 3n/5. This is a single pass, so O(n).
Q: How many repetitions are needed to boost the success probability from 1/5 to at least 99%?
A: Each trial fails with probability at most 4/5. After k trials, all fail with probability at most (4/5)^k. We need (4/5)^k ≤ 0.01, giving k ≥ log(0.01)/log(0.8) ≈ 20.6. So 21 trials suffice.
Q: Why is the total running time O(n) and not O(kn)?
A: Because k is a constant (21), O(kn) = O(21n) = O(n). The constant factor does not change the asymptotic class.
The "boost by repetition" technique connects to the BPP complexity class, where any algorithm with a constant gap between acceptance and rejection probabilities can be amplified to near-certainty. The near-median problem itself feeds back into Quicksort: using a near-median pivot guarantees O(n log n) worst-case (with high probability), bridging the gap between expected-time and high-probability guarantees.
Near median, approximate median, randomised selection, rank, order statistics, probability amplification, boosting, repetition, Quicksort pivot, expected time vs high probability, BPP, Monte Carlo algorithm, Las Vegas algorithm, EECS 376