Question bank — Linear time selection — median of medians algorithm

False. It finds a pivot $M$ that is merely "near-central"; the actual median is found by the outer Select recursion, which uses $M$ only to shrink the search. See Quickselect.

False in the sense that matters: both are $O(n)$ for the value you get. MoM's bound is worst-case, Quickselect's is expected — same asymptotic per call, but MoM has a larger constant factor.

False in general, but there is a clean criterion: for an odd group size $g$, half the $n/g$ medians and $\frac{g+1}{2}$ elements per group are $\le M$, giving surviving fraction $\frac{g+1}{2}\cdot \frac{1}{2}\cdot \frac{1}{g}$ discarded per side; linearity needs $\frac{1}{g}+\left(1-\frac{g+1}{4g}\right)<1$, which simplifies to $g\ge 5$. So $g=3$ fails, and every odd $g\ge 5$ (5, 7, 9, …) works.

False. Larger groups make the per-group median cost grow and shrink the $T(n/g)$ term, but the constant for finding each median rises. Size 5 is the sweet spot in practice, not the largest legal size.

False — it counts elements $\le M$ (the group medians themselves are included). The strict-vs-nonstrict distinction is why the 3-way $L,E,G$ split exists to handle ties.

False. Finding the median of $n/5$ items is itself a selection problem; done naively (e.g. by sorting) it costs $O(\frac{n}{5}\log \frac{n}{5})$, breaking linearity. The $T(n/5)$ term must be a real recursive Select.

False. The two children have different sizes, so it isn't a balanced tree. Linearity comes from the geometric shrinkage of total work per level (see Master Theorem doesn't directly apply — this needs the substitution method), not from depth.

False. It guarantees at least $\frac{3n}{10}$ elements on each side, so the pivot's rank lies between $\frac{3n}{10}$ and $\frac{7n}{10}$ — a wide but bounded band, which is all linearity needs.

The count is per-group medians, not all elements. Only ~half the $n/5$ groups have median $\le M$, and only 3 of the 5 in each count, giving $3\cdot \frac{n}{10}=\frac{3n}{10}$ — not $n$.

The surviving (larger) side has at most $n-\frac{3n}{10}=\frac{7n}{10}$ elements, so the term is $T(7n/10)$. The $\frac{3n}{10}$ is what we discard guarantee, not what we recurse on.

The conclusion ($10cn$) is right but the reasoning is loose: the two subproblems aren't at the same tree level, so you can't treat $\frac{9}{10}$ as a single per-level ratio. The correct argument is substituting $T(n)\le an$ and solving $a\ge 10c$.

With groups of 3, the median plus 1 smaller element = 2 per group over half the $n/3$ groups gives $\frac{2n}{6}=\frac{n}{3}$ guaranteed per side, so surviving side $\le \frac{2n}{3}$, and $\frac{1}{3}+\frac{2}{3}=1$ — still fails. No counting trick fixes size 3.

With many duplicates of $M$, a 2-way split can send an $\Omega (n)$ block into one side that fails to shrink, risking non-termination or $O(n^2)$. The $E$ bucket lets us answer instantly when $k$ falls in the equal range.

MoM is fully deterministic — no coin flips. Its $O(n)$ is worst-case, which is precisely the property that distinguishes it from randomized Quickselect.

4 is even, so a group of 4 has no single middle element — the median is ambiguous, and picking either middle weakens the "3 elements per group" count. Odd sizes give a clean single median; 5 is the smallest odd size whose fractions sum below 1.

If they summed to exactly 1 (or more), substituting $T(n)\le an$ leaves no slack to absorb the $+cn$ term — you'd need $cn\le 0$, impossible. The strict gap $\frac{1}{10}$ is exactly what pays for the linear work.

Using $M$ as Quicksort's pivot guarantees each partition splits at least $\frac{3n}{10}$ / $\frac{7n}{10}$, bounding depth at $O(\log n)$ and total cost at $O(n\log n)$ worst-case — killing Quicksort's $O(n^2)$ adversary.

Its constant factor is large (two recursive calls per level plus grouping overhead), so introselect or randomized Quickselect beats it on typical inputs. MoM is a guarantee and a building block, not a speed champion.

Because a group of 5 is constant size — sorting it costs a fixed number of comparisons no matter how big $n$ is — so all $\frac{n}{5}$ groups together cost $O(n)$. The trap is imagining the per-group cost grows with $n$; it does not, because the group size is a constant.

The classic Master Theorem is stated for the form $aT(n/b)+f(n)$ — one subproblem size $n/b$ repeated $a$ times. MoM's two children have different sizes ($n/5$ and $7n/10$), so that classic form doesn't apply; we instead guess $T(n)\le an$ and verify (see Recurrence relations).

The recursion bottoms out: sort the $\le 5$ elements directly and index position $k-1$. This constant-size base case is what stops the $T(n/5)$ recursion from spinning forever.

Write $n=5q+r$ with $0\le r<5$; there are $\lceil n/5\rceil$ groups, one possibly short. Even after rounding, at least $\lfloor \frac{1}{2}\lceil n/5\rceil \rfloor$ full groups sit on $M$'s small side, each contributing 3 elements, so the count is $\frac{3n}{10}-O(1)$ — the $-O(1)$ from rounding is absorbed by the constant $c$. Correctness is unaffected; only the constant shifts slightly.

Every group median is that value, $M$ equals it, so $L$ and $G$ are empty and $E$ holds everything. The code answers in one step via the $E$ branch — no infinite recursion, thanks to the 3-way split.

MoM still routes through the pivot: it recurses toward the correct extreme, discarding a constant fraction each call. It does not short-circuit to a linear scan, but it stays $O(n)$ regardless.

There is no $k$-th order statistic, so robust Select must reject this up front (return an error / raise), before the base case runs. Without the guard, index arithmetic like $k-1$ can silently return garbage or crash.

They all land in $E$, never split across $L$ and $G$. If $\text{len}(L)<k\le \text{len}(L)+\text{len}(E)$ we return $M$ immediately; otherwise we recurse on the strictly-greater side, which is guaranteed smaller.

Selection is undefined — there is no $k$-th element. A correct implementation guards against it before the base case; the recurrence assumes $n\ge 1$.