Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 6 / c

Assume $1\le i\le n$. Apply a worst-case $\Theta (n\log n)$ comparison sort, such as merge sort or heapsort, to the whole array, then copy its first $i$ entries to the output. The copying costs $\Theta (i)$, soThe comparison sorting lower bound makes the full-sort stage tight. For the sample array, the sorted order begins $2,6,7$, which is the required prefix for $i=3$. This method spends time ordering all $n-i$ unreported elements as well.

Store the array as a binary heap with min-heap order. Build it bottom-up by sifting down internal nodes in reverse order, rather than inserting all $n$ values one at a time. The sum of subtree heights is $O(n)$, so construction costs $\Theta (n)$. Then perform $i$ minimum extractions: output the root, move the last remaining entry to the root, and sift it down to restore the heap order.

Each extraction returns the smallest remaining key, so the outputs are the $i$ smallest keys in increasing order. For a heap of current size $s$, an extraction takes $O(\log (s+1))$ time. HenceThe tight worst-case bound for this ordinary binary heap implementation isWhen the extraction term is substantial, worst-case extractions follow root-to-leaf paths of logarithmic length; when $i$ is small, the linear construction already dominates. The bound stays valid at $i=n$, since $\log (n!)=\Theta (n\log n)$. Building by $n$ separate insertions would lose the linear construction bound and is unnecessary.

Use deterministic median of medians to select the element of rank $i$ in worst-case $\Theta (n)$ time. Partition the array about that value, retaining the $i$ smallest elements. The input is a set, so there are no equal-key ambiguities: take the $i-1$ smaller values and the selected value itself. Sort these $i$ elements with merge sort, then output them.

For completeness, median of medians groups values in fives, finds each small group's median, recursively selects a median of those medians as a pivot, and recurses only into the partition containing the requested rank. At least $3n/10-O(1)$ entries lie on each side of the pivot. Its worst-case recurrence isSelection and partitioning cost $\Theta (n)$, and sorting the retained prefix costs $\Theta (i\log i)$ for $i\ge 2$. Including output at $i=1$ givesScanning the input is necessary even to identify its minimum. Ordering the selected $i$ distinct values also has the comparison sorting lower bound $\Omega (i\log i)$, so this is asymptotically optimal for the task. A usual randomized Quickselect gives linear expected selection time, but its quadratic worst case would not establish the requested worst-case guarantee.