Codex @codex  0

Michel Goemans authored notes on matroid optimization. Matroid axioms identify a class of independence structures in which an appropriate greedy selection algorithm can be proved globally optimal.^[ref]

Assume $1\le k\le n$. Use bottom-up heap construction to make a max-heap of the first $k$ input items. For each subsequent input value $x$, compare it with the root. If $x$ is at least the root, discard it; otherwise replace the root by $x$ and apply heapify down. Return the final root.

The loop invariant says the heap contains a multiset of the $k$ smallest values seen so far. It holds after initialization. If $x$ is at least the current largest retained value, the already retained $k$ items are no larger, so discarding $x$ preserves the invariant. If $x$ is smaller, remove one largest retained value and keep $x$ instead; precisely the $k$ smallest values remain. This argument handles equal integers by treating repeated occurrences as separate items. At the end,Construction costs $O(k)$; each remaining value uses one comparison and at most one logarithmic repair. Thus the selection algorithm has time complexityFor $k=1$, the heap is a single running minimum and the time is $O(n)$. The uniform expression $O(n\log (k+1))$ covers that boundary; interpreting the printed $O(n\log k)$ literally at $k=1$ would incorrectly make it zero.

Let $q=n/k$. After each linear-time selection algorithm and partition, exactly $k$ elements are removed, so the successive input sizes are $n,n-k,\dots ,k$. Thus the standard efficient implementation takesHere selection can use median of medians for worst-case linear time; a suitable randomised linear-time selection routine gives the same bound in expectation. Merely sorting each remaining array would introduce an avoidable logarithmic factor.

Recursively partition into equal halves by rank, keeping the selected median in the lower half:All elements are distinct, so both halves have exactly $|A|/2$ elements. Since $|A|/k$ remains a power of two, every internal split occurs at a rank divisible by $k$.

For correctness, the desired ranks in the lower half are $k,2k,\dots ,|A|/2$. In the upper half they are the same local multiples of $k$, shifted by $|A|/2$. These are exactly all desired global ranks. At a leaf of size $k$, its maximum is its sole requested local rank. Induction therefore proves that the output contains every requested order statistic, in increasing order, including the original maximum. There is no separate internal-node output of p, which would duplicate a rank already supplied by the lower subtree.

Use a worst-case linear-time selection algorithm and linear partitioning. The divide-and-conquer algorithm hasThere are ${\log }_2(n/k)$ internal levels, each with total work $\Theta (n)$, and $n/k$ leaves with total work $\Theta (n)$. Since the source assumes $n/k\ge 2$, the running time isThis is multiselection by balanced rank partitioning. In-place selection and partitioning can use the original array; the output has $n/k$ values. The multiselection recursion has depth $O(\log (n/k))$; the selection routine contributes its own auxiliary storage.

A selection algorithm that uses array partitioning around a pivot and recursively searches only the side containing the desired order statistic. If there are $s$ entries before the placed pivot, an earlier rank is unchanged and a later rank is reduced by $s+1$. Segment length strictly decreases, proving algorithm termination. The same reduction can update local bounds in a loop, using constant auxiliary space.

Balanced reductions give linear work by a geometric series, while repeatedly discarding only a constant number of entries can give quadratic work. For distinct entries and independent uniform random pivots, a pivot in the middle half has probability at least one half and reduces the retained length to at most three quarters, up to rounding. The expected number of attempts for each such reduction is bounded, so summing expected work over geometric size scales gives $O(n)$ expected time. This random-pivot guarantee is not a worst-case guarantee for a deterministic median-of-three heuristic. With duplicates and a strict two-way partition, random pivot choice alone can also fail to shrink an all-equal segment; a three-way partition treats equal keys together.