On efficiency analysis of randomized divide-and-conquer median find

Question

I read following explanation from Dasgupta's Algorithms book for Median finding, this is the same philosophy applied in randomized quick-sort. Here as per book terminology $S$ denotes array of integers, $v$ is pivot, $S_{L}$ and $S_{R}$ are left and right side of pivot element.

To distinguish between lucky and unlucky choices of $v$, we will call $v$ good if it lies within the 25th to 75th percentile of the array that it is chosen from. We like these choices of $v$ because they ensure that the sub lists $S_{L}$ and $S_{R}$ have size at most three-fourths that of $S$ (do you see why?), so that the array shrinks substantially. Fortunately, good $v$’s are abundant: half the elements of any list must fall between the 25th to 75th percentile!

In one of the interview it was asked to me up till what range this median finding gives average running time of $n$. i.e. Favourable range of selection is within 25 to 75 percentile. But up to what extent we can reduce this and still have average running time of $n$

My approach was to write recurrence relation and then from the height of the tree comment on average running time, but I doubt is it a correct way to have answer? Also it might not provide tighter bounds.

It will be helpful if someone can also suggest what mathematical tool/technique will be useful for this kind of analysis.

Answer 1

There's no need to do any calculation. There is absolutely nothing special about the numbers 25 and 75.

If $0 < \alpha < \beta < 1$ and you are promised that the median is between the $\alpha$'th percentile and the $\beta$'th percentile, then the running time of the algorithm will be linear. Indeed, if $\gamma = \min(\alpha,1-\beta)$, the length reduces by a factor of at least $1-\gamma$ in each recursive call, so the total running time will be proportional to at most $$ n \sum_{i=0}^\infty (1-\gamma)^i. $$ Even without computing the sum, we can tell that in converges, so we get a bound of $O(n)$. If we compute the sum, we get the dependence on $\gamma$: $$ \frac{n}{\gamma}. $$

This sort of behavior always occurs when we reduce a problem to a subproblem which is smaller by a constant factor bounded away from 1. Once you know that, you don't need to do any calculations.